Efficient discrete-time simulations of continuous-time quantum query algorithms
arXiv:0811.4428 · doi:10.1145/1536414.1536471
Abstract
The continuous-time query model is a variant of the discrete query model in which queries can be interleaved with known operations (called "driving operations") continuously in time. Interesting algorithms have been discovered in this model, such as an algorithm for evaluating nand trees more efficiently than any classical algorithm. Subsequent work has shown that there also exists an efficient algorithm for nand trees in the discrete query model; however, there is no efficient conversion known for continuous-time query algorithms for arbitrary problems. We show that any quantum algorithm in the continuous-time query model whose total query time is T can be simulated by a quantum algorithm in the discrete query model that makes O[T log(T) / log(log(T))] queries. This is the first upper bound that is independent of the driving operations (i.e., it holds even if the norm of the driving Hamiltonian is very large). A corollary is that any lower bound of T queries for a problem in the discrete-time query model immediately carries over to a lower bound of Ω[T log(log(T))/log (T)] in the continuous-time query model.
12 pages, 6 figs
References in corpus (10)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Mechanics helps in searching for a needle in a haystack
- Quantum Computation and Decision Trees
- Exponential algorithmic speedup by quantum walk
- Efficient quantum algorithms for simulating sparse Hamiltonians
- On the relationship between continuous- and discrete-time quantum walk
- Introduction to Quantum Computation
- Hamiltonian Oracles
- Approximating Fractional Time Quantum Evolution
- Every NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer
Cited by in corpus (17)
- Optimal Hamiltonian Simulation by Quantum Signal Processing
- On the relationship between continuous- and discrete-time quantum walk
- Exponential improvement in precision for simulating sparse Hamiltonians
- Quantum query complexity of state conversion
- Exponentially more precise quantum simulation of fermions I: Quantum chemistry in second quantization
- Hamiltonian Simulation Using Linear Combinations of Unitary Operations
- Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function
- Floating Point Representations in Quantum Circuit Synthesis
- Analog Nature of Quantum Adiabatic Unstructured Search
- Nonlinear Quantum Search Using the Gross-Pitaevskii Equation
- Query-optimal estimation of unitary channels in diamond distance
- Approximating Fractional Time Quantum Evolution
- Variations on Quantum Adversary
- The Promise of Quantum Simulation
- How Quantum is the Speedup in Adiabatic Unstructured Search?
- Ancilla Approximable Quantum State Transformations
- Nonlinear Quantum Search