Bremner, MJ, Jozsa, R & Shepherd, DJ 2011, 'Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy', PROCEEDINGS OF THE ROYAL SOCIETY A-MATHEMATICAL PHYSICAL AND ENGINEERING SCIENCES, vol. 467, no. 2126, pp. 459-472.
View/Download from: Publisher's site
View description>>
We consider quantum computations comprising only commuting gates, known as IQP computations, and provide compelling evidence that the task of sampling their output probability distributions is unlikely to be achievable by any efficient classical means. More specifically, we introduce the class post-IQP of languages decided with bounded error by uniform families of IQP circuits with post-selection, and prove first that post-IQP equals the classical class PP. Using this result we show that if the output distributions of uniform IQP circuit families could be classically efficiently sampled, either exactly in total variation distance or even approximately up to 41 per cent multiplicative error in the probabilities, then the infinite tower of classical complexity classes known as the polynomial hierarchy would collapse to its third level. We mention some further results on the classical simulation properties of IQP circuit families, in particular showing that if the output distribution results from measurements on only O(log n) lines then it may, in fact, be classically efficiently sampled.
Chen, J, Chen, X, Duan, R, Ji, Z & Zeng, B 2011, 'No-go theorem for one-way quantum computing on naturally occurring two-level systems', Physical Review A, vol. 83, no. 5, pp. 0-0.
View/Download from: Publisher's site
View description>>
The ground states of some many-body quantum systems can serve as resource states for the one-way quantum computing model, achieving the full power of quantum computation. Such resource states are found, for example, in spin- 5 2 and spin- 3 2 systems. It is, of course, desirable to have a natural resource state in a spin- 1 2 , that is, qubit system. Here, we give a negative answer to this question for frustration-free systems with two-body interactions. In fact, it is shown to be impossible for any genuinely entangled qubit state to be a nondegenerate ground state of any two-body frustration-free Hamiltonian. What is more, we also prove that every spin- 1 2 frustration-free Hamiltonian with two-body interaction always has a ground state that is a product of single- or two-qubit states. In other words, there cannot be any interesting entanglement features in the ground state of such a qubit Hamiltonian.
Chen, J, Ji, Z, Klyachko, A, Kribs, DW & Zeng, B 2011, 'Rank Reduction for the Local Consistency Problem', JOURNAL OF MATHEMATICAL PHYSICS, vol. 53, no. 2.
View/Download from: Publisher's site
View description>>
We address the problem of how simple a solution can be for a given quantumlocal consistency instance. More specifically, we investigate how small therank of the global density operator can be if the local constraints are knownto be compatible. We prove that any compatible local density operators can besatisfied by a low rank global density operator. Then we study both fermionicand bosonic versions of the N-representability problem as applications. Afterapplying the channel-state duality, we prove that any compatible local channelscan be obtained through a global quantum channel with small Kraus rank.
Chen, J, Ji, Z, Kribs, D, Wei, Z & Zeng, B 2011, 'Ground-State Spaces of Frustration-Free Hamiltonians', JOURNAL OF MATHEMATICAL PHYSICS, vol. 53, no. 10.
View/Download from: Publisher's site
View description>>
We study the ground-state space properties for frustration-free Hamiltonians.We introduce a concept of `reduced spaces' to characterize local structures ofground-state spaces. For a many-body system, we characterize mathematicalstructures for the set $\Theta_k$ of all the $k$-particle reduced spaces, whichwith a binary operation called join forms a semilattice that can be interpretedas an abstract convex structure. The smallest nonzero elements in $\Theta_k$,called atoms, are analogs of extreme points. We study the properties of atomsin $\Theta_k$ and discuss its relationship with ground states of $k$-localfrustration-free Hamiltonians. For spin-1/2 systems, we show that all the atomsin $\Theta_2$ are unique ground states of some 2-local frustration-freeHamiltonians. Moreover, we show that the elements in $\Theta_k$ may not be thejoin of atoms, indicating a richer structure for $\Theta_k$ beyond the convexstructure. Our study of $\Theta_k$ deepens the understanding of ground-statespace properties for frustration-free Hamiltonians, from a new angle of reducedspaces.
Chen, J, Ji, Z, Wei, Z & Zeng, B 2011, 'Correlations in excited states of local Hamiltonians', PHYSICAL REVIEW A, vol. 85, no. 4.
View/Download from: Publisher's site
View description>>
Physical properties of the ground and excited states of a $k$-localHamiltonian are largely determined by the $k$-particle reduced density matrices($k$-RDMs), or simply the $k$-matrix for fermionic systems---they are at leastenough for the calculation of the ground state and excited state energies.Moreover, for a non-degenerate ground state of a $k$-local Hamiltonian, eventhe state itself is completely determined by its $k$-RDMs, and thereforecontains no genuine ${>}k$-particle correlations, as they can be inferred from$k$-particle correlation functions. It is natural to ask whether a similarresult holds for non-degenerate excited states. In fact, for fermionic systems,it has been conjectured that any non-degenerate excited state of a 2-localHamiltonian is simultaneously a unique ground state of another 2-localHamiltonian, hence is uniquely determined by its 2-matrix. And a weaker versionof this conjecture states that any non-degenerate excited state of a 2-localHamiltonian is uniquely determined by its 2-matrix among all the pure$n$-particle states. We construct explicit counterexamples to show that bothconjectures are false. It means that correlations in excited states of localHamiltonians could be dramatically different from those in ground states. Wefurther show that any non-degenerate excited state of a $k$-local Hamiltonianis a unique ground state of another $2k$-local Hamiltonian, hence is uniquelydetermined by its $2k$-RDMs (or $2k$-matrix).
Chen, J, Ji, Z, Zeng, B & Zhou, DL 2011, 'From Ground States to Local Hamiltonians', PHYSICAL REVIEW A, vol. 86, no. 2.
View/Download from: Publisher's site
View description>>
Traditional quantum physics solves ground states for a given Hamiltonian,while quantum information science asks for the existence and construction ofcertain Hamiltonians for given ground states. In practical situations, onewould be mainly interested in local Hamiltonians with certain interactionpatterns, such as nearest neighbour interactions on some type of lattices. Anecessary condition for a space $V$ to be the ground-state space of some localHamiltonian with a given interaction pattern, is that the maximally mixed statesupported on $V$ is uniquely determined by its reduced density matricesassociated with the given pattern, based on the principle of maximum entropy.However, it is unclear whether this condition is in general also sufficient. Weexamine the situations for the existence of such a local Hamiltonian to have$V$ satisfying the necessary condition mentioned above as its ground-statespace, by linking to faces of the convex body of the local reduced states. Wefurther discuss some methods for constructing the corresponding localHamiltonians with given interaction patterns, mainly from physical points ofview, including constructions related to perturbation methods, localfrustration-free Hamiltonians, as well as thermodynamical ensembles.
Datta, A, Zhang, L, Nunn, J, Langford, NK, Feito, A, Plenio, MB & Walmsley, IA 2011, 'A compact entanglement distillery', Phys. Rev. Lett., vol. 108, no. 6, pp. 060502-060502.
View/Download from: Publisher's site
View description>>
Large-scale quantum-correlated networks could transform technologies rangingfrom communications and cryptography to computation, metrology, and simulationof novel materials. Critical to achieving such quantum enhancements isdistributing high-quality entanglement between distant nodes. This is madepossible in the unavoidable presence of decoherence by entanglementdistillation. However, current versions of this protocol are prohibitivelycostly in terms of resources. We introduce a new scheme for continuous-variableentanglement distillation that requires only linear temporal and constantphysical or spatial resources, both of which are exponential improvements overexisting protocols. Our scheme uses a fixed module - an entanglement distillery- comprising only four quantum memories of at most 50 % storage efficiency andallowing a feasible experimental implementation. Tangible quantum advantagesare obtained by using non-ideal quantum memories outside their conventionalrole of storage. By creating, storing and processing information in the samephysical space, the scheme establishes a potentially valuable technique fordesigning stable, scalable protocols across different quantum technologies.
Devitt, SJ, Stephens, AM, Munro, WJ & Nemoto, K 2011, 'Integration of highly probabilistic sources into optical quantum architectures: perpetual quantum computation', New J. Phys. 13: 095001 (2011), vol. 13.
View/Download from: Publisher's site
View description>>
In this paper we introduce a design for an optical topological cluster statecomputer constructed exclusively from a single quantum component. Unlikeprevious efforts we eliminate the need for on demand, high fidelity photonsources and detectors and replace them with the same device utilised to createphoton/photon entanglement. This introduces highly probabilistic elements intothe optical architecture while maintaining complete specificity of thestructure and operation for a large scale computer. Photons in this system arecontinually recycled back into the preparation network, allowing for aarbitrarily deep 3D cluster to be prepared using a comparatively small numberof photonic qubits and consequently the elimination of high frequency,deterministic photon sources.
Ferrie, C, Granade, CE & Cory, DG 2011, 'How to best sample a periodic probability distribution, or on the accuracy of Hamiltonian finding strategies', QUANTUM INFORMATION PROCESSING, vol. 12, no. 1, pp. 611-623.
View/Download from: Publisher's site
View description>>
Projective measurements of a single two-level quantum mechanical system (aqubit) evolving under a time-independent Hamiltonian produce a probabilitydistribution that is periodic in the evolution time. The period of thisdistribution is an important parameter in the Hamiltonian. Here, we explore howto design experiments so as to minimize error in the estimation of thisparameter. While it has been shown that useful results may be obtained byminimizing the risk incurred by each experiment, such an approach iscomputationally intractable in general. Here, we motivate and derive heuristicstrategies for experiment design that enjoy the same exponential scaling asfully optimized strategies. We then discuss generalizations to the case offinite relaxation times, T_2 < \infty.
Furrer, F, Franz, T, Berta, M, Leverrier, A, Scholz, VB, Tomamichel, M & Werner, RF 2011, 'Continuous Variable Quantum Key Distribution: Finite-Key Analysis of Composable Security against Coherent Attacks', Phys. Rev. Lett., vol. 109, no. 10, p. 100502.
View/Download from: Publisher's site
View description>>
We provide a security analysis for continuous variable quantum keydistribution protocols based on the transmission of squeezed vacuum statesmeasured via homodyne detection. We employ a version of the entropicuncertainty relation for smooth entropies to give a lower bound on the numberof secret bits which can be extracted from a finite number of runs of theprotocol. This bound is valid under general coherent attacks, and gives rise tokeys which are composably secure. For comparison, we also give a lower boundvalid under the assumption of collective attacks. For both scenarios, we findpositive key rates using experimental parameters reachable today.
Gerrits, T, Thomas-Peter, N, Gates, JC, Lita, AE, Metcalf, BJ, Calkins, B, Tomlin, NA, Fox, AE, Linares, AL, Spring, JB, Langford, NK, Mirin, RP, Smith, PGR, Walmsley, IA & Nam, SW 2011, 'On-chip, photon-number-resolving, telecommunication-band detectors for scalable photonic information processing', Physical Review A, vol. 84, no. 6.
View/Download from: Publisher's site
Jain, R, Ji, Z, Upadhyay, S & Watrous, J 2011, 'QIP = PSPACE', Journal of the ACM, vol. 58, no. 6, pp. 1-27.
View/Download from: Publisher's site
View description>>
This work considers the quantum interactive proof system model of computation, which is the (classical) interactive proof system model’s natural quantum computational analogue. An exact characterization of the expressive power of quantum interactive proof systems is obtained: the collection of computational problems having quantum interactive proof systems consists precisely of those problems solvable by deterministic Turing machines that use at most a polynomial amount of space (or, more succinctly, QIP = PSPACE). This characterization is proved through the use of a parallelized form of the matrix multiplicative weights update method, applied to a class of semidefinite programs that captures the computational power of quantum interactive proof systems. One striking implication of this characterization is that quantum computing provides no increase in computational power whatsoever over classical computing in the context of interactive proof systems, for it is well known that the collection of computational problems having classical interactive proof systems coincides with those problems solvable by polynomial-space computations.
Ji, Z, Wei, Z & Zeng, B 2011, 'Complete characterization of the ground-space structure of two-body frustration-free Hamiltonians for qubits', Physical Review A, vol. 84, no. 4.
View/Download from: Publisher's site
Kieferova, M & Nagaj, D 2011, 'Quantum Walks on Necklaces and Mixing', Issue, vol. 2, p. 1250025.
View description>>
We analyze continuous-time quantum walks on necklace graphs - cyclical graphsconsisting of many copies of a smaller graph (pearl). Using a Bloch-type ansatzfor the eigenfunctions, we block-diagonalize the Hamiltonian, reducing theeffective size of the problem to the size of a single pearl. We then present ageneral approach for showing that the mixing time scales (with growing size ofthe necklace) similarly to that of a simple walk on a cycle. Finally, wepresent results for mixing on several necklace graphs.
Langford, NK, Ramelow, S, Prevedel, R, Munro, WJ, Milburn, GJ & Zeilinger, A 2011, 'Efficient quantum computing using coherent photon conversion', Nature, vol. 478, no. 7369, pp. 360-363.
View/Download from: Publisher's site
Lapkiewicz, R, Li, P, Schaeff, C, Langford, NK, Ramelow, S, Wieśniak, M & Zeilinger, A 2011, 'Experimental non-classicality of an indivisible quantum system', Nature, vol. 474, no. 7352, pp. 490-493.
View/Download from: Publisher's site
Lee, KC, Sprague, MR, Sussman, BJ, Nunn, J, Langford, NK, Jin, X-M, Champion, T, Michelberger, P, Reim, KF, England, D, Jaksch, D & Walmsley, IA 2011, 'Entangling Macroscopic Diamonds at Room Temperature', Science, vol. 334, no. 6060, pp. 1253-1256.
View/Download from: Publisher's site
View description>>
Optical pulses are used to quantum mechanically entangle two diamonds several centimeters apart.
Liu, W & Li, S 2011, 'On standard models of fuzzy region connection calculus', International Journal of Approximate Reasoning, vol. 52, no. 9, pp. 1337-1354.
View/Download from: Publisher's site
View description>>
The Region Connection Calculus (RCC) is perhaps the most influential topological relation calculus. Based on the first-order logic, the RCC, however, does not fully meet the needs of applications where the vagueness of entities or relations is important and not ignorable. This paper introduces standard models for the fuzzy region connection calculus (RCC) proposed by Schockaert et al. (2008) [18]. Each of such a standard fuzzy RCC model is induced by a standard RCC model in a natural way. We prove that each standard fuzzy RCC model is canonical in the sense that any satisfiable set of fuzzy RCC8 constraints have a solution in it. Apolynomial realization algorithm is also provided. As a side product,we showsimilar sets of fuzzy constraints have similar solutions if both are satisfiable. This allows us to approximate fuzzy RCC constraints that have arbitrary bounds by those have bounds with finite precision. © 2011 Published by Elsevier Inc.
Mans, B & Mathieson, L 2011, 'On the Treewidth of Dynamic Graphs', Theoretical Computer Science, vol. 554, no. C, pp. 217-228.
View/Download from: Publisher's site
View description>>
Dynamic graph theory is a novel, growing area that deals with graphs thatchange over time and is of great utility in modelling modern wireless, mobileand dynamic environments. As a graph evolves, possibly arbitrarily, it ischallenging to identify the graph properties that can be preserved over timeand understand their respective computability. In this paper we are concerned with the treewidth of dynamic graphs. We focuson metatheorems, which allow the generation of a series of results based ongeneral properties of classes of structures. In graph theory two majormetatheorems on treewidth provide complexity classifications by employingstructural graph measures and finite model theory. Courcelle's Theorem gives ageneral tractability result for problems expressible in monadic second orderlogic on graphs of bounded treewidth, and Frick & Grohe demonstrate a similarresult for first order logic and graphs of bounded local treewidth. We extend these theorems by showing that dynamic graphs of bounded (local)treewidth where the length of time over which the graph evolves and is observedis finite and bounded can be modelled in such a way that the (local) treewidthof the underlying graph is maintained. We show the application of these resultsto problems in dynamic graph theory and dynamic extensions to static problems.In addition we demonstrate that certain widely used dynamic graph classesnaturally have bounded local treewidth.
McPeak, KM, Le, TP, Britton, NG, Nickolov, ZS, Elabd, YA & Baxter, JB 2011, 'Chemical Bath Deposition of ZnO Nanowires at Near-Neutral pH Conditions without Hexamethylenetetramine (HMTA): Understanding the Role of HMTA in ZnO Nanowire Growth', Langmuir, vol. 27, no. 7, pp. 3672-3677.
View/Download from: Publisher's site
Ocko, SA, Chen, X, Zeng, B, Yoshida, B, Ji, Z, Ruskai, MB & Chuang, IL 2011, 'Quantum Codes Give Counterexamples to the Unique Preimage Conjecture of theN-Representability Problem', Physical Review Letters, vol. 106, no. 11.
View/Download from: Publisher's site
Reim, KF, Michelberger, P, Lee, KC, Nunn, J, Langford, NK & Walmsley, IA 2011, 'Single-Photon-Level Quantum Memory at Room Temperature', Physical Review Letters, vol. 107, no. 5.
View/Download from: Publisher's site
Szehr, O, Dupuis, F, Tomamichel, M & Renner, R 2011, 'Decoupling with unitary approximate two-designs', New J. Phys., vol. 15, p. 053022.
View/Download from: Publisher's site
View description>>
Consider a bipartite system, of which one subsystem, A, undergoes a physicalevolution separated from the other subsystem, R. One may ask under whichconditions this evolution destroys all initial correlations between thesubsystems A and R, i.e. decouples the subsystems. A quantitative answer tothis question is provided by decoupling theorems, which have been developedrecently in the area of quantum information theory. This paper builds onpreceding work, which shows that decoupling is achieved if the evolution on Aconsists of a typical unitary, chosen with respect to the Haar measure,followed by a process that adds sufficient decoherence. Here, we prove ageneralized decoupling theorem for the case where the unitary is chosen from anapproximate two-design. A main implication of this result is that decoupling isphysical, in the sense that it occurs already for short sequences of randomtwo-body interactions, which can be modeled as efficient circuits. Ourdecoupling result is independent of the dimension of the R system, which showsthat approximate 2-designs are appropriate for decoupling even if the dimensionof this system is large.
Thomas-Peter, N, Langford, NK, Datta, A, Zhang, L, Smith, BJ, Spring, JB, Metcalf, BJ, Coldenstrodt-Ronge, HB, Hu, M, Nunn, J & Walmsley, IA 2011, 'Integrated Photonic Sensing', New J. Phys., vol. 13, p. 055024.
View/Download from: Publisher's site
View description>>
Loss is a critical roadblock to achieving photonic quantum-enhancedtechnologies. We explore a modular platform for implementing integratedphotonics experiments and consider the effects of loss at different stages ofthese experiments, including state preparation, manipulation and measurement.We frame our discussion mainly in the context of quantum sensing and focusparticularly on the use of loss-tolerant Holland-Burnett states for opticalphase estimation. In particular, we discuss spontaneous four-wave mixing instandard birefringent fibre as a source of pure, heralded single photons andpresent methods of optimising such sources. We also outline a route toprogrammable circuits which allow the control of photonic interactions even inthe presence of fabrication imperfections and describe a ratiometriccharacterisation method for beam splitters which allows the characterisation ofcomplex circuits without the need for full process tomography. Finally, wepresent a framework for performing state tomography on heralded states usinglossy measurement devices. This is motivated by a calculation of the effects offabrication imperfections on precision measurement using Holland-Burnettstates.
Tomamichel, M & Hänggi, E 2011, 'The Link between Entropic Uncertainty and Nonlocality', J. Phys. A: Math. Theor., vol. 46, no. 5, p. 055301.
View/Download from: Publisher's site
View description>>
Two of the most intriguing features of quantum physics are the uncertaintyprinciple and the occurrence of nonlocal correlations. The uncertaintyprinciple states that there exist pairs of incompatible measurements on quantumsystems such that their outcomes cannot both be predicted. On the other hand,nonlocal correlations of measurement outcomes at different locations cannot beexplained by classical physics, but appear in the presence of entanglement.Here, we show that these two fundamental quantum effects are quantitativelyrelated. Namely, we provide an entropic uncertainty relation for the outcomesof two binary measurements, where the lower bound on the uncertainty isquantified in terms of the maximum Clauser-Horne-Shimony-Holt value that can beachieved with these measurements. We discuss applications of this uncertaintyrelation in quantum cryptography, in particular, to certify quantum sourcesusing untrusted devices.
Tomamichel, M, Lim, CCW, Gisin, N & Renner, R 2011, 'Tight Finite-Key Analysis for Quantum Cryptography', Nat. Commun., vol. 3, pp. 634-6.
View/Download from: Publisher's site
View description>>
Despite enormous progress both in theoretical and experimental quantumcryptography, the security of most current implementations of quantum keydistribution is still not established rigorously. One of the main problems isthat the security of the final key is highly dependent on the number, M, ofsignals exchanged between the legitimate parties. While, in any practicalimplementation, M is limited by the available resources, existing securityproofs are often only valid asymptotically for unrealistically large values ofM. Here, we demonstrate that this gap between theory and practice can beovercome using a recently developed proof technique based on the uncertaintyrelation for smooth entropies. Specifically, we consider a family ofBennett-Brassard 1984 quantum key distribution protocols and show that securityagainst general attacks can be guaranteed already for moderate values of M.
Winkler, S, Tomamichel, M, Hengl, S & Renner, R 2011, 'Impossibility of Growing Quantum Bit Commitments', Phys. Rev. Lett., vol. 107, no. 9, p. 090502.
View/Download from: Publisher's site
View description>>
Quantum key distribution (QKD) is often, more correctly, called key growing.Given a short key as a seed, QKD enables two parties, connected by an insecurequantum channel, to generate a secret key of arbitrary length. Conversely, nokey agreement is possible without access to an initial key. Here, we consideranother fundamental cryptographic task, commitments. While, similar to keyagreement, commitments cannot be realized from scratch, we ask whether they maybe grown. That is, given the ability to commit to a fixed number of bits, isthere a way to augment this to commitments to strings of arbitrary length?Using recently developed information-theoretic techniques, we answer thisquestion to the negative.
Ying, M 2011, 'Floyd-Hoare Logic for Quantum Programs', ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, vol. 33, no. 6, pp. 1-49.
View/Download from: Publisher's site
View description>>
Floyd-Hoare logic is a foundation of axiomatic semantics of classical programs, and it provides effective proof techniques for reasoning about correctness of classical programs. To offer similar techniques for quantum program verification and to build a logical foundation of programming methodology for quantum computers, we develop a full-fledged Floyd-Hoare logic for both partial and total correctness of quantum programs. It is proved that this logic is (relatively) complete by exploiting the power of weakest preconditions and weakest liberal preconditions for quantum programs. © 2011 ACM.
Ying, M & Feng, Y 2011, 'A Flowchart Language for Quantum Programming', IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, vol. 37, no. 4, pp. 466-485.
View/Download from: Publisher's site
View description>>
Several high-level quantum programming languages have been proposed in the previous research. In this paper, we define a low-level flowchart language for quantum programming, which can be used in implementation of high-level quantum languages and in design of quantum compilers. The formal semantics of the flowchart language is given, and the notion of correctness for programs written in this language is introduced. A structured quantum programming theorem is presented, which provides a technique of translating quantum flowchart programs into programs written in a high-level language, namely, a quantum extension of the while-language. © 2006 IEEE.
Ying, M, Yu, N, Feng, Y & Duan, R 2011, 'Verification of Quantum Programs', CoRR, vol. abs/1106.4063, no. 4, pp. 1085-1093.
View/Download from: Publisher's site
View description>>
© Copyright 2018, Institute of Software, the Chinese Academy of Sciences. All rights reserved. With the rapid development of quantum hardware, people tend to believe that special-purpose quantum computers with more than 100 qubits will be available in 5 to 10 years. It is conceivable that, once this becomes a reality, the development of quantum software will be crucial in harnessing the power of quantum computers. However, due to the distinguishable features of quantum mechanics, such as the no-cloning of quantum information and the nonlocal effect of entanglement, developing correct and efficient quantum programs and communication protocols is a challenging issue. Formal verification methods, particularly model checking techniques, have proven effective in classical software design and system modelling. Therefore, formal verification of quantum software has received more and more attention recently. This article reviews recent research findings in verification of both sequential quantum programs and quantum communication protocols, with the focus placed on the work of the two authors' research groups. Future directions and challenges in this area are also discussed.
Yu, N, Duan, R & Ying, M 2011, 'Any 2 circle times n subspace is locally distinguishable', PHYSICAL REVIEW A, vol. 84, no. 1, pp. 1-3.
View/Download from: Publisher's site
View description>>
A subspace of a multipartite Hilbert space is said to be locally indistinguishable if any orthonormal basis of this subspace cannot be perfectly distinguished by local operations and classical communication. Previously it was shown that any m . n bipartite system with m > 2 and n > 2 has a locally indistinguishable subspace. However, it has been an open problem since 2005 whether there is a locally indistinguishable bipartite subspace with a qubit subsystem.We settle this problem in negative by showing that any 2 . n bipartite subspace contains a basis that is locally distinguishable. As an interesting application, we show that any quantum channel with two Kraus operators has optimal environment-assisted classical capacity.
Arefin, AS, Inostroza-Ponta, M, Mathieson, L, Berretta, R & Moscato, P 1970, 'Clustering Nodes in Large-Scale Biological Networks Using External Memory Algorithms', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), International Conference on Algorithms and Architectures for Parallel Processing, Springer Berlin Heidelberg, Melbourne, Australia, pp. 375-386.
View/Download from: Publisher's site
View description>>
Novel analytical techniques have dramatically enhanced our understanding of many application domains including biological networks inferred from gene expression studies. However, there are clear computational challenges associated to the large datasets generated from these studies. The algorithmic solution of some NP-hard combinatorial optimization problems that naturally arise on the analysis of large networks is difficult without specialized computer facilities (i.e. supercomputers). In this work, we address the data clustering problem of large-scale biological networks with a polynomial-time algorithm that uses reasonable computing resources and is limited by the available memory. We have adapted and improved the MSTkNN graph partitioning algorithm and redesigned it to take advantage of external memory (EM) algorithms. We evaluate the scalability and performance of our proposed algorithm on a well-known breast cancer microarray study and its associated dataset. © 2011 Springer-Verlag.
Babai, L, Codenotti, P, Grochow, JA & Qiao, Y 1970, 'Code Equivalence and Group Isomorphism', Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, San Francisco, USA, pp. 1395-1408.
View/Download from: Publisher's site
View description>>
The isomorphism problem for groups given by their multiplication tables has long been known to be solvable in time nlog n+O(1). The decades-old quest for a polynomial-time algorithm has focused on the very difficult case of class-2 nilpotent groups (groups whose quotient by their center is abelian), with little success. In this paper we consider the opposite end of the spectrum and initiate a more hopeful program to find a polynomial-time algorithm for semisimple groups, defined as groups without abelian normal subgroups. First we prove that the isomorphism problem for this class can be solved in time nO(log log n). We then identify certain bottlenecks to polynomial-time solvability and give a polynomial-time solution to a rich subclass, namely the semisimple groups where each minimal normal subgroup has a bounded number of simple factors. We relate the results to the filtration of groups introduced by Babai and Beals (1999). One of our tools is an algorithm for equivalence of (not necessarily linear) codes in simply-exponential time in the length of the code, obtained by modifying Luks's algorithm for hypergraph isomorphism in simply-exponential time in the number of vertices (FOCS 1999). We comment on the complexity of the closely related problem of permutational isomorphism of permutation groups.
Bremner, MJ 1970, 'Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy', 14th Workshop on Quantum Information Processing, Singapore.
View description>>
Quantum Information Processing (QIP) is a rapidly developing field of research spanning both physics and computer science. As the name implies, the field extends information processing (including computing and cryptography) to physical regimes where quantum effects become significant. QIP 2011 was the fourteenth workshop on theoretical aspects of quantum computing, quantum cryptography, and quantum information in a series that started in Aarhus in 1998 and was held 2010 at ETH Zurich, Switzerland. QIP 2011 featured a tutorial programme, invited talks, contributed talks, and a poster session. In addition, there was a rump session with short informal talks.
Devitt, SJ, Stephens, AM, Munro, WJ & Nemoto, K 1970, 'Integration of highly probabilistic sources into optical quantum architectures', Optics InfoBase Conference Papers, pp. 423-425.
View description>>
We introduce a design for an optical computer constructed exclusively from a single quantum component. Unlike previous efforts we eliminate the need for on demand photon sources and detectors and replace them with the same device utilised to create photon/photon entanglement. This introduces highly probabilistic elements into the architecture while maintaining complete specificity of the structure and operation for a large-scale computer. © 2011 AOS.
Devitt, SJ, Stephens, AM, Munro, WJ & Nemoto, K 1970, 'Integration of highly probabilistic sources into optical quantum architectures.', Proceedings of the International Quantum Electronics Conference and Conference on Lasers and Electro-Optics Pacific Rim 2011, International Quantum Electronics Conference, OSA, pp. I715-I715.
View/Download from: Publisher's site
View description>>
We introduce a design for an optical computer constructed exclusively from a single quantum component. Unlike previous efforts we eliminate the need for on demand photon sources and detectors and replace them with the same device utilised to create photon/photon entanglement. This introduces highly probabilistic elements into the architecture while maintaining complete specificity of the structure and operation for a large scale computer. © 2011 Optical Society of America.
Devitt, SJ, Stephens, AM, Munro, WJ & Nemoto, K 1970, 'The optical quantum computer: how big and how fast?', SPIE Proceedings, SPIE Optical Engineering + Applications, SPIE, San Diego, CA, pp. 81630R-81630R.
View/Download from: Publisher's site
Feng, Y, Duan, R & Ying, M 1970, 'Bisimulation for Quantum Processes', ACM SIGPLAN NOTICES, ACM-SIGACT Symposium on Principles of Programming Languages, ACM, Austin, Texas, USA, pp. 523-534.
View/Download from: Publisher's site
View description>>
Quantum cryptographic systems have been commercially available, with a striking advantage over classical systems that their security and ability to detect the presence of eavesdropping are provable based on the principles of quantum mechanics. On the other hand, quantum protocol designers may commit much more faults than classical protocol designers since human intuition is much better adapted to the classical world than the quantum world. To offer formal techniques for modeling and verification of quantum protocols, several quantum extensions of process algebra have been proposed. One of the most serious issues in quantum process algebra is to discover a quantum generalization of the notion of bisimulation, which lies in a central position in process algebra, preserved by parallel composition in the presence of quantum entanglement, which has no counterpart in classical computation. Quite a few versions of bisimulation have been defined for quantum processes in the literature, but in the best case they are only proved to be preserved by parallel composition of purely quantum processes where no classical communications are involved. Many quantum cryptographic protocols, however, employ the LOCC (Local Operations and Classical Communications) scheme, where classical communications must be explicitly specified. So, a notion of bisimulation preserved by parallel composition in the circumstance of both classical and quantum communications is crucial for process algebra approach to verification of quantum cryptographic protocols. In this paper we introduce a novel notion of bisimulation for quantum processes and prove that it is congruent with respect to various process algebra combinators including parallel composition even when both classical and quantum communications are present.We also establish some basic algebraic laws for this bisimulation.
Feng, Y, Duan, R, Ying, M & ACM 1970, 'Bisimulation for Quantum Processes', POPL 11: PROCEEDINGS OF THE 38TH ANNUAL ACM SIGPLAN-SIGACT SYMPOSIUM ON PRINCIPLES OF PROGRAMMING LANGUAGES, 38th Symposium on Principles of Programming Languages, ASSOC COMPUTING MACHINERY, Austin, TX, pp. 523-534.
View/Download from: Publisher's site
Lee, T & Roland, J 1970, 'A strong direct product theorem for quantum query complexity', 27th IEEE Conference on Computational Complexity (CCC'12), pages 236-246, 2012, 2012 IEEE Conference on Computational Complexity (CCC), IEEE, Porto, Portugal.
View/Download from: Publisher's site
View description>>
We show that quantum query complexity satisfies a strong direct producttheorem. This means that computing $k$ copies of a function with less than $k$times the quantum queries needed to compute one copy of the function impliesthat the overall success probability will be exponentially small in $k$. For aboolean function $f$ we also show an XOR lemma---computing the parity of $k$copies of $f$ with less than $k$ times the queries needed for one copy impliesthat the advantage over random guessing will be exponentially small. We do this by showing that the multiplicative adversary method, whichinherently satisfies a strong direct product theorem, is always at least aslarge as the additive adversary method, which is known to characterize quantumquery complexity.
Liu, W, Wang, S-S, Li, S & Liu, D 1970, 'Solving Qualitative Constraints Involving Landmarks.', CP, International Conference on Principles and Practice, Springer, Perugia, Italy, pp. 523-537.
View/Download from: Publisher's site
View description>>
Consistency checking plays a central role in qualitative spatial and temporal reasoning. Given a set of variables V , and a set of constraints Î taken from a qualitative calculus (e.g. the Interval Algebra (IA) or RCC-8), the aim is to decide if Î is consistent. The consistency problem has been investigated extensively in the literature. Practical applications e.g. urban planning often impose, in addition to those between undetermined entities (variables), constraints between determined entities (constants or landmarks) and variables. This paper introduces this as a new class of qualitative constraint satisfaction problems, and investigates the new consistency problem in several well-known qualitative calculi, e.g. IA, RCC-5, and RCC-8.We show that the usual local consistency checking algorithm works for IA but fails in RCC-5 and RCC-8. We further show that, if the landmarks are represented by polygons, then the new consistency problem of RCC-5 is tractable but that of RCC-8 is NP-complete.
Munro, WJ, Devitt, SJ & Nemoto, K 1970, 'Designing quantum repeaters and networks', SPIE Proceedings, SPIE Optical Engineering + Applications, SPIE, San Diego, CA, pp. 816307-816307.
View/Download from: Publisher's site
Munro, WJ, Devitt, SJ, Stephens, AM, Nemoto, K, Ralph, T & Lam, PK 1970, 'High Bandwidth Quantum Communication', AIP Conference Proceedings, QUANTUM COMMUNICATION, MEASUREMENT AND COMPUTING (QCMC): The Tenth International Conference, AIP, Brisbane, AUSTRALIA, pp. 47-50.
View/Download from: Publisher's site
Munro, WJ, Stephens, AM, Devitt, SJ & Nemoto, K 1970, 'Quantum communication without memories or shared entanglement', Optics InfoBase Conference Papers, pp. 413-414.
View description>>
Long-range quantum communication and its associated repeater network are a necessity for any future quantum Internet. The performance of such networks is currently limited by the time it takes to establish entangled links between the appropriate parties on the network. Typically this scales as the round trip time for a signal to be transmitted between those parties. We present in this talk the design of a communications network for the direct transfer of quantum information where the rate at which quantum data can be transmitted is not limited by the distance the information needs to be sent but instead by the time to perform efficient local gate operations. Our scheme requires neither the establishment of entanglement between communication nodes nor the use of long-lived quantum memories. Our scheme thus provides a much higher communications rate than in standard teleportation based schemes. © 2011 AOS.
Munro, WJ, Stephens, AM, Devitt, SJ & Nemoto, K 1970, 'Quantum communication without memories or shared entanglement', 2011 International Quantum Electronics Conference (IQEC) and Conference on Lasers and Electro-Optics (CLEO) Pacific Rim incorporating the Australasian Conference on Optics, Lasers and Spectroscopy and the Australian Conference on Optical Fibre Technology, 2011 International Quantum Electronics Conference (IQEC) and Conference on Lasers and Electro-Optics (CLEO) Pacific Rim, IEEE, pp. 413-414.
View/Download from: Publisher's site
View description>>
Long-range quantum communication and its associated repeater network are a necessity for any future quantum Internet. The performance of such networks is currently limited by the time it takes to establish entangled links between the appropriate parties on the network. Typically this scales as the round trip time for a signal to be transmitted between those parties. We present in this talk the design of a communications network for the direct transfer of quantum information where the rate at which quantum data can be transmitted is not limited by the distance the information needs to be sent but instead by the time to perform efficient local gate operations. Our scheme requires neither the establishment of entanglement between communication nodes nor the use of long-lived quantum memories. Our scheme thus provides a much higher communications rate than in standard teleportation based schemes. © 2011 IEEE.
Munro, WJ, Stephens, AM, Devitt, SJ & Nemoto, K 1970, 'Quantum Communication without memories or shared entanglement', Proceedings of the International Quantum Electronics Conference and Conference on Lasers and Electro-Optics Pacific Rim 2011, International Quantum Electronics Conference, OSA, pp. I182-I182.
View/Download from: Publisher's site
Nemoto, K, Devitt, SJ, Stephens, AM & Munro, WJ 1970, 'Integration of highly probabilistic sources into optical quantum architectures', International Conference on Quantum Information, International Conference on Quantum Information, OSA, pp. QTuC2-QTuC2.
View/Download from: Publisher's site
Qiao, Y, Jayalal, SMN & Tang, B 1970, 'On isomorphism testing of groups with normal hall subgroups', Leibniz International Proceedings in Informatics, LIPIcs, 28th International Symposium on Theoretical Aspects of Computer Science (SATCS), SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS, Dortmund, GERMANY, pp. 567-578.
View/Download from: Publisher's site
View description>>
A normal Hall subgroup N of a group G is a normal subgroup with its order coprime with its index. Schur-Zassenhaus theorem states that every normal Hall subgroup has a complement subgroup, that is a set of coset representatives H which also forms a subgroup of G. In this paper, we present a framework to test isomorphism of groups with at least one normal Hall subgroup, when groups are given as multiplication tables. To establish the framework, we first observe that a proof of Schur-Zassenhaus theorem is constructive, and formulate a necessary and sufficient condition for testing isomorphism in terms of the associated actions of the semidirect products, and isomorphisms of the normal parts and complement parts. We then focus on the case when the normal subgroup is abelian. Utilizing basic facts of representation theory of finite groups and a technique by Le Gall in [9], we first get an efficient isomorphism testing algorithm when the complement has bounded number of generators. For the case when the complement subgroup is elementary abelian, which does not necessarily have bounded number of generators, we obtain a polynomial time isomorphism testing algorithm by reducing to generalized code isomorphism problem. A solution to the latter can be obtained by a mild extension of the singly exponential (in the number of coordinates) time algorithm for code isomorphism problem developed recently by Babai in [3]. Enroute to obtaining the above reduction, we study the following computational problem in representation theory of finite groups: given two representations ρ and τ of a group H over ℤdp, p a prime, determine if there exists an automorphism φ: H → H, such that the induced representation ρφ = ρ o φ and τ are equivalent, in time poly(|H|,pd). © Youming Qiao, Jayalal Sarma M.N., and Bangsheng Tang.
Reim, KF, Michelberger, P, Lee, KC, Nunn, J, Langford, NK & Walmsley, AI 1970, 'Single-photon-level memory at room temperature', Optics InfoBase Conference Papers.
Reim, KF, Michelberger, P, Lee, KC, Nunn, J, Langford, NK & Walmsley, IA 1970, 'Single-photon-level memory at room temperature', 2011 Conference on Lasers and Electro-Optics Europe and 12th European Quantum Electronics Conference (CLEO EUROPE/EQEC), 12th European Quantum Electronics Conference CLEO EUROPE/EQEC, IEEE, pp. 1-1.
View/Download from: Publisher's site
View description>>
Quantum memories capable of storing single photons are essential building blocks for quantum information processing, enabling the storage and transfer of quantum information over long distances [1]. Devices operating at room temperature can be deployed on a large scale and integrated into existing photonic networks, but so far warm quantum memories have been susceptible to noise at the single photon level [2]. Using a fundamentally different approach to quantum memories, i.e. the recently developed far off-resonant Raman memory scheme [3], we present a highly efficient room-temperature memory that is able to operate with a low unconditional noise floor in the quantum regime, something that no other room-temperature memory has been able to demonstrate before. The quantum memory is operated in warm caesium vapour, and the long-lived, 9.2 GHz hyperfine-split states of the caesium D2 line serve as ground and storage states. The laser fields are 15 GHz detuned from the excited state. © 2011 IEEE.
Reim, KF, Michelberger, P, Lee, KC, Nunn, J, Langford, NK & Walmsley, IA 1970, 'Single-photon-level memory at room temperature', CLEO:2011 - Laser Applications to Photonic Applications, Quantum Electronics and Laser Science Conference, OSA, pp. QThJ1-QThJ1.
View/Download from: Publisher's site
View description>>
We present an efficient broadband optical single-photon-level room-temperature memory, capable of operating with a low unconditional noise floor in the quantum regime, with memory efficiencies exceeding 30% and storage times of up to 4 μs. © 2011 OSA.
Reim, KF, Michelberger, P, Lee, KC, Nunn, J, Langford, NK & Walmsley, IA 1970, 'Single-photon-level memory at room temperature', Optics InfoBase Conference Papers.
View description>>
We present an efficient broadband optical single-photon-level room-temperature memory, capable of operating with a low unconditional noise floor in the quantum regime, with memory efficiencies exceeding 30% and storage times of up to 4 μs. © 2011 Optical Society of America.
Runyao Duan, Severini, S & Winter, A 1970, 'Zero-error communication via quantum channels and a quantum Lovász θ-function', 2011 IEEE International Symposium on Information Theory Proceedings, 2011 IEEE International Symposium on Information Theory - ISIT, IEEE, St Petersburg, Russia, pp. 64-68.
View/Download from: Publisher's site
View description>>
We study the quantum channel version of Shannon's zero-error capacity problem. Motivated by recent progress on this question, we propose to consider a certain linear space operators as the quantum generalisation of the adjacency matrix, in terms of which the plain, quantum and entanglement-assisted capacity can be formulated, and for which we show some new basic properties. Most importantly, we define a quantum version of Lova´sz' famous ? function, as the norm-completion (or stabilisation) of a naive generalisation of ?. We go on to show that this function upper bounds the number of entanglement-assisted zero-error messages, that it is given by a semidefinite programme, whose dual we write down explicitly, and that it is multiplicative with respect to the natural (strong) graph product. We explore various other properties of the new quantity, which reduces to Lova´sz' original ? in the classical case, give several applications, and propose to study the linear spaces of operators associated to channels as non-commutative graphs, using the language of operator systems and Hilbert modules.
Walmsley, IA, Nunn, J, Langford, N, Datta, A, Zhang, L, Smith, B, Thomas-Peter, N, Spring, J, Metcalf, B, Englland, D, Reim, K, Michelberger, P & Champion, T 1970, 'Building multimode quantum optical networks', Optics InfoBase Conference Papers.
View description>>
Light offers a route to the generation of macroscopic quantum states based on both multiple photons (e.g. Schrödinger kittens) and multiple modes (e.g. Dicke-Werner). The combination of these approaches affords new possibilities in both fundamental physics and in technological applications. The routes to building scalabl networks embodying such systems from feasible laboratory resources will be discussed. © 2011 OSA.
Walmsley, IA, Nunn, J, Langford, N, Datta, A, Zhang, L, Smith, B, Thomas-Peter, N, Spring, J, Metcalf, B, Englland, D, Reim, K, Michelberger, P & Champion, T 1970, 'Building multimode quantum optical networks', Frontiers in Optics 2011/Laser Science XXVII, Laser Science, OSA, pp. LTuF1-LTuF1.
View/Download from: Publisher's site
Walmsley, IA, Nunn, J, Langford, N, Reim, K, Michelberger, P & Champion, T 1970, 'Photonic quantum memories', Optics InfoBase Conference Papers.
View description>>
We survey the state of the art in photonic quantum memories, describing different approaches to the storage and manipulation of quantum light beams and pulses, and expected applications.
Walmsley, IA, Nunn, J, Langford, N, Reim, K, Michelberger, P & Champion, T 1970, 'Photonic quantum memories', 2011 Conference on Lasers and Electro-Optics Europe and 12th European Quantum Electronics Conference (CLEO EUROPE/EQEC), 12th European Quantum Electronics Conference CLEO EUROPE/EQEC, IEEE, pp. 1-1.
View/Download from: Publisher's site
View description>>
We survey the state of the art in photonic quantum memories, describing different approaches to the storage and manipulation of quantum light beams and pulses, and expected applications. © 2011 IEEE.
Zhang, H, Zhang, Y, Ying, M & Zhou, Y 1970, 'Translating First-Order Theories into Logic Programs.', IJCAI, International Joint Conference on Artificial Intelligence, IJCAI/AAAI, Barcelona, pp. 1126-1131.
View/Download from: Publisher's site
View description>>
This paper focuses on computing first-order theories under either stable model semantics or circumscription. A reduction from first-order theories to logic programs under stable model semantics over finite structures is proposed, and an embedding of circumscription into stable model semantics is also given. Having such reduction and embedding, reasoning problems represented by first-order theories under these two semantics can then be handled by using existing answer set solvers. The effectiveness of this approach in computing hard problems beyond NP is demonstrated by some experiments.
