Adiabatic quantum state generation and statistical zero knowledge

By Dorit Aharonov, Amnon Ta-Shma. Symposium on the Theory of Computing, 2003

438 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/6842b39fbeae22082bbee45db18478b2c7b455c1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Quantum algorithm for linear systems of equations. (2008, neutral): “[27] D.”
Universal computation by quantum walk. (2008, background): “ca two models are equivalent, since the quantum walk on any sufficiently sparse graph can be efficiently simulated by a universal quantum computer [4, 21, 22, 23].”
Polynomial-time quantum algorithm for the simulation of chemical dynamics (2008, background): “The preparation of an arbitrary quantum state is exponentially hard, in general (29).”
Hamiltonian Simulation by Qubitization (2016, methodology): “The ﬁrst explicit quantum algorithms were discovered by Lloyd [31] for local interactions, and then generalized by Aharonov and Ta-Shma [3] to sparse Hamiltonians.”
Optimal Hamiltonian Simulation by Quantum Signal Processing. (2016, background): “Following seminal work by Lloyd [11] for Hamiltonians with local interactions, and Aharonov and TaShma [12] for more general sparse Hamiltonians, many celebrated results have been obtained over the years [13– 19] for approximating the time evolution operator e−iĤt”
Quantum random walks: An introductory overview (2003, background): “However it has been shown recently [39, 40] that simulation of continuous time random walks can be done eﬃciently on a quantum computer.”
Quantum walks: a comprehensive review (2012, background): “As in [113], the number of quantum wires in a graph G will grow exponentially with respect to the number of qubits to be employed but, as previously stated in the beginning of this section, both G and the propagation of a discrete-time quantum walk on it are to be simulated by a general purpose quan”
High-order quantum algorithm for solving linear differential equations (2010, background): “Therefore the amplitude would not drop below the amplitude on the eigenspace corresponding to the largest eigenvalue.”
Adiabatic quantum computation is equivalent to standard quantum computation (2004, background): “[21] left the main question of universality of adiabatic computation with phy sically realistic (namely, local) Hamiltonians, open.”
Improved techniques for preparing eigenstates of fermionic Hamiltonians (2017, background): “(4), are discussed in,(55) related to the sparse decompositions first described in.(56) If U is not Hermitian, then we may construct a Hermitian V as”
Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters (2015, background): “Sparse Hamiltonians include most physically realistic Hamiltonians as a special case (making these algorithms potentially useful for simulating real-world systems).”
On the Relationship Between Continuous- and Discrete-Time Quantum Walk (2008, methodology): “Finally, I discuss limitations of the method for simulating Hamiltonians with negative matrix elements, and present two problems that motivate attempting to circumvent these limitations.”