QUROPE Quantum Information Processing and Communication in Europe

4.3.1 THEORY OF QUANTUM CUMPUTING

Quantum algorithms and complexity

Following Deutsch’s fundamental work in 1985 that demonstrated the potential power of quantum algorithms and quantum computers, Shor demonstrated in 1994 that integers can be efficiently factorized on a quantum computer. Factoring is the task of decomposing an integer, say 15, into a product of prime numbers: 15=3*5. Its importance is immense because many modern cryptographic protocols (for instance the famous RSA cryptosystem) are based on the fact that factoring large integers, as well as computing discrete logarithms, is a hard problem on a classical computer. Shor’s result means that quantum computers could crack most classical public-key cryptosystems used at present. It has lead to extensive work on developing new quantum algorithms. Progress has been made on the Hidden Subgroup problem (which generalizes Shor’s algorithm) in the case of non-Abelian groups, like affine groups, the dihedral group, or solvable groups with small exponent. A quantum algorithm was discovered for finding solutions to Pell’s equation, which is an important problem in algebraic number theory. Strong links have been established between known quantum algorithms and lattice problems. Finally Grover’s quantum “data base” search algorithm allows a quantum computer to perform an unstructured search quadratically faster than any classical algorithm. Although Grover's only yields a quadratic speed-up over classical algorithms it can be widely used in computer science tasks, like sorting, matrix multiplication bipartite matching to name a few. For all these problems quantum computers give an important advantage over classical computers. Grover's algorithms can be cast in terms of quantum random walks which has lead recently to new quantum algorithms for searching game trees. These algorithms will be widely applicable in the area of algorithmic game theory, scientific computing etc.

Very recently a new quantum algorithm has been developed for approximating solutions to linear equations. This algorithm demonstrates an exponential advantage over any classical algorithm. In order to understand to what extent quantum computers outperform classical computers we need to determine where efficient quantum computation, BQP, fits within the classification of complexity classes, like P, NP, and PSPACE. General methods for proving impossibility results, that is limitations of quantum computers, have been developed and applied with great success. Notable are the polynomial method and the quantum adversary method.

Key references
[1] D. Deutsch, "Quantum theory, the Church-Turing principle and the universal quantum computer", Proc. R. Soc. Lond. A 400, 97 (1985)
[2] P. W. Shor, "Algorithms for quantum computation, discrete log and factoring", FOCS’35, 124 (1994)
[3] L. Grover, "A fast quantum mechanical algorithm for database search", STOC’28, 212 (1996)
[4] A. Ambainis, D. Aharonov, J. Kempe and U. Vazirani, "Quantum walks on graphs", 33rd ACM Symp. on Theory of Computing (2001)
[5] R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf, "Quantum lower bounds by polynomials",Journal of the ACM 48(4) (2001)
[6] A. Ambainis, "Quantum lower bounds by quantum arguments", Journal of Computer and System Sciences 64, 750 (2002)
[7] E. Farhi, J. Goldstone and S. Gutmann. "A Quantum Algorithm for the Hamiltonian NAND Tree" [ quant-ph/0702144]
[8] A. W. Harrow, A. Hassidim, and S. Lloyd, "Quantum algorithm for solving linear systems of equations", Phys. Rev. Lett. 15, 150502 (2009)

Quantum communication protocols

Following the success of quantum algorithms quantum communication complexity was developed by initial work of Yao (qubit model) and Cleve and Buhrman (entanglement assisted model). The setting is that of multiple quantum computers trying to solve computational tasks, minimizing the amount of communication. There has also been considerable development of new protocols for quantum communication over the last decade. Useful protocols that found applications outside that of communication complexity are Quantum Fingerprinting and the Hidden Matching problem. These protocols demonstrate an exponential improvement in the communication over classical protocols. Applications are in many areas, like interactive games and approximation algorithms, lower bound for classical and quantum computers, as well as the development of new non-locality tests. Main open questions in this area are to understand the power that entanglement assisted model offers. This is poorly understood, but recently some progress has been made by connecting this question for restricted games, called XOR games, to functional analysis. An intriguing interplay between quantum communications complexity, non-locality, approximation algorithms, and functional analysis is becoming available.

Key references
[1] A. Yao, "Quantum circuit complexity", Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science, 352 (1993)
[2] H. Buhrman, R. Cleve, and A. Wigderson, "Quantum vs. classical communication and computation", Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC 1998)
[3] R. Cleve, P. Høyer, B. Toner, and J. Watrous, "Consequences and limits of nonlocal strategies", Proc. of 19th IEEE Conference on Computational Complexity (2004)
[4] D. Gavinsky, J. Kempe, I. Kerenidis, R. Raz, and R. de Wolf, "Exponential separations for one-way quantum communication complexity, with applications to cryptography", SIAM Journal on Computing, 38, 1695 (2008)
[5] Z. Bar-Yossef, T. S. Jayram, I. Kerenidis, "Exponential separation of quantum and classical one-way communication complexity", SIAM J. Comput. 38 (2008)
[6] J. Briët, H. Buhrman, T. Lee, and T. Vidick, "Multiplayer XOR games and quantum communication complexity with clique-wise entanglement", [quant-ph/0911.4007]
[7] H. Buhrman, R. Cleve, S. Massar, and R. de Wolf, "Nonlocality and communication complexity", Rev. Mod. Phys. 81 (2010)

Quantum cryptographic protocols

The most import feat of quantum computers is that they can efficiently factor integers into their prime factors. This in turns means that most of the cryptographic protocols that are used today, whose security is based on the assumption that factoring is hard, will be rendered obsolete once a quantum computer is built. But all is not lost, quantum information processing opens up possibilities that are classically impossible. The well known key distribution protocol, due to Bennett and Brassard, establishes that two parties, who trust each other, can generate a secret shared key in such a way that if there is an eavesdropper trying to obtain the key or part thereof, will be detected with high probability. Once a secure key is established classical protocols, like the one-time pad, allow for secure message transmission. Such secure key distribution schemes are classically impossible! Moreover quantum key distribution schemes (QKD) are already commercially available.

It is natural and important to figure out what other protocols are possible using quantum technology. Unfortunately it was realized by Mayers, Lo and Chau that the schemes that are rendered insecure by Shor's factoring algorithm, asymmetric or public key cryptography, can not be unconditionally secure in the quantum world, something that KQD is. This again does not mean all is lost. Quantum information processing is able to realize tasks which are impossible classically such as biased Coin Tossing and Quantum Bit String Generation, Quantum String Commitment, resilient and unconditionally secure Digital Signatures, or Private Information Retrieval. We expect that the existing protocols will be improved and will gradually be implemented in the laboratory (as was recently the case for quantum bit string generation). We also expect the development of new protocols for quantum communication.

Another strand has initiated secure protocols under mild assumptions. A very promising one is the bounded storage model. The assumption is that it is impossible to build quantum memories that store reliably huge amounts of qubits for a few seconds. Currently storing reliably a single qubit for a millisecond is already very challenging. It turns out that schemes, similar in flavor to QKD, allow for secure, under the bounded storage assumption, quantum implementations of a primitive called oblivious transfer (OT). Having this primitive as a building block allows one to build all cryptographic schemes that are used in practice today. More important these implementations appear technically not much more demanding than those of QKD.

However when have built a quantum computer that is able to efficiently and reliably factor integers, we need to find cryptographic protocols that are secure under computational assumptions, like current cryptographic protocols are secure under the assumption that factoring is hard. This line of research is part of post quantum cryptography. Progress has been made by Regev who developed a protocol based on the hardness of certain lattice problems. But these schemes are still too inefficient to be of practical use.

Key references
[1] C. H. Bennett and G. Brassard, “Quantum cryptography: Public key distribution and coin tossing”, in Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing, Bangalore, p. 175 (1984)
[2] A. Ambainis, “A new protocol and lower bounds for quantum coin flipping”, Journal of Computer and System Sciences, 134 (2004).
[3] A. Chailloux and I. Kerenidis, “Optimal quantum strong coin flipping”, 50th Annual Symposium on Foundations of Computer Science (FOCS) (2009).
[4] H. Buhrman, M. Christandl, P. Hayden, and H-K. Lo, and S. Wehner, “Security of quantum bit string commitment depends on the information measure”, Phys. Rev. Lett. 97, 250501 (2006).
[5] L-P. Lamoureux, E. Brainis, D. Amans, J. Barrett, and S. Massar “Provably secure experimental quantum bit-string generation”, Phys. Rev. Lett. 94, 050503(4) (2005).
[6] O. Regev, “On lattices, learning with errors, random linear codes, and cryptography”, In Proc. 37th ACM Symp. on Theory of Computing (STOC), 84 (2005).

Computational models and architectures

There are many different ideas of how to make quantum systems compute. While these different computational models are typically equivalent in the sense that one can simulate the other with only polynomial overheads in resources, they may be quite different in practice, when it comes to a particular class of problems. They also have to satify very different needs from the perspective of the requirements on the hardware. What is more, they suggest different procedures to achieve fault tolerant computation, many of them yet to be explored in detail. At the moment the main contenders of fundamental architectures are:

• The gate or circuit model (computation realized by series of elementary unitary transformations on a few qubits at a time);
• The one-way quantum computer (computation realized by sequence of 1-bit measurements on a pre-entangled cluster state) and alternative, more general schemes for measurement-based quantum computing;
• Adiabatic computing (computation realized by smoothly changing a Hamiltonian, whose ground state, at the end of the process, encodes the solution of the given problem);
• Quantum cellular automata (quantum versions of classical cellular automata);
• Quantum Turing machines (quantum versions of classical Turing machines);
• Dissipation-driven quantum computation (computation realized by dissipative dynamics). 

Most recently, we have seen a series of theoretical work analyzing the connection between the different computational models. The benefit of these works lies in a better understanding of the capabilities and advantages of the individual models, and of the essential features of a quantum computer. It will also turn out what model will eventually give rise to the most feasible architecture. In the future we expect that optimized models (i.e. taking the best out of the different approaches) will be developed. We also expect that these models will have an increasing impact on (i) the formulation of new quantum algorithms and (ii) the evaluation of physical systems regarding their suitability for fault-tolerant quantum computation. Both of these points are of great importance for the field: While new algorithms will further enlarge the range of applications for quantum computers, new methods for fault-tolerant computation will hopefully make it technologically less challenging to realize scalable quantum computers in the laboratory.

Key references[1] D. Deutsch, "Quantum computational networks", Proc. R. Soc. Lond. A 425, 73 (1989)
[2] A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter, "Elementary gates for quantum computation", Phys. Rev. A 52, 3457 (1995)
[3] E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, "A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem", Science 292, 472 (2001)
[4] B. Schumacher and R. Werner, "Reversible cellular automata", [quant-ph/0405174]
[5] R. Raussendorf and H.-J. Briegel, "A one-way quantum computer", Phys. Rev. Lett. 86, 5188 (2001)
[6] D. Gross and J. Eisert, "Novel schemes for measurement-based quantum computation", Phys. Rev. Lett. 98, 220503 (2007)
[7] S. Diehl, A. Micheli, A. Kantian, B. Kraus, H. P. Büchler, and P. Zoller, "Quantum states and phases in driven open quantum systems with cold atoms", Nature Physics 4, 878 (2008)
[8] F. Verstraete, M. M. Wolf, and J. I. Cirac, "Quantum computation, quantum state engineering, and quantum phase transitions driven by dissipation", Nature Physics 5, 633 (2009)

Quantum simulation

Quantum simulators may become the first application of quantum computers, since with modest requirements one may be able to perform simulations which are impossible with classical computers. At the beginning of the 80's it was realized that it will be impossible to predict and describe the properties of certain quantum systems using classical computers, since the number of variables that must be stored grows exponentially with the number of particles. A quantum system in which the interactions between the particles could be engineered would be able to simulate that system in a very efficient way. This would then allow, for example, studying the microscopic properties of interesting materials permitting free variation of system parameters. Potential outcomes would be to obtain an accurate description of chemical compounds and reactions, to gain deeper understanding of high temperature superconductivity, or to find out the reason why quarks are always confined.

A quantum simulator is a quantum system whose dynamics can be engineered such that it reproduces the behaviour of another physical system which one is interested to describe. In principle, a quantum computer would be an almost perfect quantum simulator since one can program it to undergo any desired quantum dynamics. However, a quantum computer is very difficult to build in practice and has very demanding requirements. Fortunately, there are physical systems in which one can engineer certain kind of interactions and thus simulate other systems which so far are not well understood. This is due to the fact that with classical computers it is impossible to reproduce their dynamics, given that the number of parameters required to represent the corresponding state grows exponentially with the number of particles.

Key examples are ultra-cold atoms in optical lattices or trapped ions, both architectures having seen great progress in recent years. In those systems, one does not necessarily require to individually address the qubits, or to perform quantum gates on arbitrary pairs of qubits, but rather on all of them at the same time. Ideas like optical superlattices or the suitable exploitation of Feshbach resonances in the former class of physical systems add further flexibility. Besides, one is interested in measuring physical properties (like magnetization, conductivity, etc.) which are robust with respect to the appearance of several errors (in a quantum computer without error correction, even a single error will destroy the computation). For example, to see whether a material is conducting or not one does not need to know with a high precision the corresponding conductivity. Molecular energies within chemical precision can also be computed by quantum simulations. Such computations are among the smallest applications of quantum computing. The use of 30 to 100 qubits for those algorithms exceeds the limitations of classical computing of molecular energies.

Key references
[1] S. Lloyd, "Universal quantum simulators", Science 273, 1073 (1996)
[2] E. Jané, G. Vidal, W. Dür, P. Zoller, and J. I. Cirac, "Simulation of quantum dynamics with quantum optical systems", Quant. Inf. Comp. 3, 15 (2003)
[3] C. H. Bennett, J. I. Cirac, M. S. Leifer, D. W. Leung, N. Linden, S. Popescu, and G. Vidal, "Optimal simulation of two-qubit Hamiltonians using general local operations", Phys. Rev. A 66, 012305 (2002)
[4] M. A. Nielsen, M. J. Bremner, J. L. Dodd, A. M. Childs, and C. M. Dawson, "Universal simulation of Hamiltonian dynamics for qudits", Phys. Rev. A 66, 022317 (2002)
[5] A. Aspuru-Guzik, A. D. Dutoi, P. J. Love, and M. Head-Gordon, “Simulated quantum computation of molecular energies”, Science 309, 1704 (2005)
[6] D. Jaksch and P. Zoller, "The cold atom Hubbard toolbox", Ann. Phys. 315, 52 (2005)
[7] M. J. Hartmann, F. G. S. L. Brandao and M. B. Plenio, "Complex dynamics in coupled arrays of micro-cavities", Laser and Photonics Reviews 6, 527 (2008)
[8] I. Bloch, J. Dalibard, and W. Zwerger, "Many-body physics with ultracold gases", Rev. Mod. Phys. 80, 885 (2008)