Adiabatic quantum state generation and statistical zero knowledge

ABSTRACT

The design of new quantum algorithms has proven to be an extremely difficult task. This paper considers a different approach to the problem, by studying the problem of 'quantum state generation'.We first show that any problem in Statistical Zero Knowledge (including eg. discrete log, quadratic residuosity and gap closest vector in a lattice) can be reduced to an instance of the quantum state generation problem. Having shown the generality of the state generation problem, we set the foundations for a new paradigm for quantum state generation. We define 'Adiabatic State Generation' (ASG), which is based on Hamiltonians instead of unitary gates. We develop tools for ASG including a very general method for implementing Hamiltonians (The sparse Hamiltonian lemma), and ways to guarantee non negligible spectral gaps (The jagged adiabatic path lemma). We also prove that ASG is equivalent in power to state generation in the standard quantum model. After setting the foundations for ASG, we show how to apply our techniques to generate interesting superpositions related to Markov chains.The ASG approach to quantum algorithms provides intriguing links between quantum computation and many different areas: the analysis of spectral gaps and groundstates of Hamiltonians in physics, rapidly mixing Markov chains, statistical zero knowledge, and quantum random walks. We hope that these links will bring new insights and methods into quantum algorithms.

REFERENCES

• 1: Scott Aaronson, Quantum lower bound for the collision problem, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509999]
• 2: D. Aharonov and A. Ta-Shma. quant-ph/0210077. A longer version of this paper.
• 3: D. Aharonov, A simple proof that Toffoli and Hadamard are quantum universal, quant-ph 0301040
• 4: N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
• 5: N. Alon and J. Spencer, The Probabilistic Method. 1991.
• 6: David Applegate , Ravi Kannan, Sampling and integration of near log-concave functions, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.156-163, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103439]
• 7: M. Born, V. Fock and B. des Adiabatensatzes. Z. Phys. 51, pp. 165--169, 1928
• 8: Russ Bubley , Martin Dyer, Faster random generation of linear extensions, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.350-354, January 25-27, 1998, San Francisco, California, United States
• 9: A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann and D. A. Spielman, Exponential algorithmic speedup by quantum walk, quant-ph/0209131
• 10: A. M. Childs, E. Deotto, E. Farhi, J. Goldstone, S. Gutmann, A. J. Landahl, Quantum search by measurement, Phys. Rev. A 66, 032314 (2002)
• 11: A. M. Childs, E. Farhi, J. Goldstone and S. Gutmann, Finding cliques by quantum adiabatic evolution, quant-ph/0012104.
• 12: A. M. Childs, E. Farhi and S. Gutmann, An example of the difference between quantum and classical random walks, quant-ph/0103020. Also, E. Farhi and S. Gutmann, Quantum computation and decision Trees, quant-ph/9706062
• 13: W. van Dam and S. Hallgren, Efficient quantum algorithms for Shifted Quadratic Character Problems, quant-ph/0011067
• 14: W. Van Dam, How Powerful is Adiabatic Quantum Computation?, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.279, October 14-17, 2001
• 15: W. van Dam and U. Vazirani, More on the power of adiabatic computation, unpublished, 2001
• 16: E. Farhi, J. Goldstone and S. Gutmann, A numerical study of the performance of a quantum adiabatic evolution algorithm for satisfiability, quant-ph/0007071.
• 17: 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), quant-ph/0104129.
• 18: E. Farhi, J. Goldstone and S. Gutmann, Quantum Adiabatic Evolution Algorithms with Different Paths, quant-ph/0208135
• 19: E. Farhi, J. Goldstone, S. Gutmann and M. Sipser, Quantum Computation by Adiabatic Evolution, quant-ph/0001106
• 20: O. Goldreich and E. Kushilevitz, A Perfect Zero-Knowledge Proof System for a Problem Equivalent to the Discrete Logarithm, Journal of Cryptology, 6(2), pp. 97--116, 1993
• 21: Oded Goldreich , Shafi Goldwasser, On the limits of non-approximability of lattice problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.1-9, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276704]
• 22: Oded Goldreich , Amit Sahai , Salil Vadhan, Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.399-408, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276852]
• 23: S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
• 24: M. Grotschel and L. Lovasz, Combinatorial Optimization: A Survey, Handbook of Combinatorics, North-Holland, 1993
• 25: L. Grover, Quantum Mechanics helps in searching for a needle in a haystack, Phys. Rev. Letters, July 14, 1997
• 26: L. Grover and T. Rudolph, Creating superpositions that correspond to efficiently integrable probability distributions, quant-ph/0208112
• 27: Sean Hallgren, Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510001]
• 28: M. Jerrum and A. Sinclair, E. Vigoda A Polynomial-Time Approximation Algorithm for the permanent of a matrix with non-negative entries, STOC 2000
• 29: Mark Jerrum , Alistair Sinclair, The Markov chain Monte Carlo method: an approach to approximate counting and integration, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 30: T. Kato, On the adiabatic theorem of Quantum Mechanics, J. Phys. Soc. Jap. 5, pp. 435--439(1951)
• 31: A. Yu. Kitaev, Quantum measurements and the Abelian Stabilizer Problem, quant-ph/9511026
• 32: Johannes Köbler , Uwe Schöning , Jacobo Torán, The graph isomorphism problem: its structural complexity, Birkhauser Verlag, Basel, Switzerland, 1994
• 33: Landau and Lifshitz, Quantum Mechanics (Second edition of English Translation), Pergamon press, 1965
• 34: L. Lovasz: Random Walks on Graphs: A Survey. Combinatorics, Paul Erdos is Eighty, Vol. 2, ed. D. Miklos, V. T. Sos, T. Szonyi, 1996, pp. 353--398.
• 35: Messiah, Quantum Mechanics, John Willey & Sons (1958)
• 36: M. A. Nielsen and I. Chuang, Quantum Computation and Information 2000
• 37: See A. Peres, Quantum Theory: Concepts and methods, 1995
• 38: J. Roland and N. Cerf, Quantum Search by Local Adiabatic Evolution Phys. Rev. A 65, 042308 (2002)
• 39: Amit Sahai , Salil Vadhan, A Complete Promise Problem for Statistical Zero-Knowledge, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.448, October 19-22, 1997
• 40: Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]
• 41: W. L. Spitzer and S. Starr, Improved bounds on the spectral gap above frustration free ground states of quantum spin chains, math-ph/0212029
• 42: Y. Shi, Both Toffoli and Controlled-NOT need little help to do universal quantum computation, quant-ph/0205115
• 43: Salil Pravin Vadhan , Shafi Goldwasser, A study of statistical zero-knowledge proofs, 1999
• 44: John Watrous, Quantum algorithms for solvable groups, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.60-67, July 2001, Hersonissos, Greece [doi>10.1145/380752.380759]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

General Terms:
Algorithms, Theory

Keywords:
Hamiltonian, Markov chains, quantum adiabatic computation, quantum sampling, spectral gap, state generation, statistical zero knowledge