Efficient discrete-time simulations of continuous-time quantum query algorithms

DOI10.1145/1536414.1536471MaRDI QIDQ5172735zbMATH OpenOpenAlexWikidataFDO

Authors Richard Cleve, Michele Mosca, R. D. Somma, David Yonge-Mallo, Daniel Gottesman

Publication date 4 February 2015

Published in Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0811.4428

zbMATH Keywords

quantum algorithmsquantum query complexity

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

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 Omega[T log(log(T))/log (T)] in the continuous-time query model.

Recommendations

• On the relationship between continuous- and discrete-time quantum walk
• A universal adiabatic quantum query algorithm
• Simulating continuous-time Hamiltonian dynamics by way of a discrete-time quantum walk
• Efficient quantum circuits for continuous-time quantum walks on composite graphs
• Exact simulation of coined quantum walks with the continuous-time model

Cited in

(10)

• Floating point representations in quantum circuit synthesis
• On the relationship between continuous- and discrete-time quantum walk
• Nonadiabatic quantum search algorithm with analytical success rate
• On the efficiency of quantum algorithms for Hamiltonian simulation
• A universal adiabatic quantum query algorithm
• Ancilla-approximable quantum state transformations
• Nonlinear quantum search using the Gross–Pitaevskii equation
• scientific article; zbMATH DE number 5320194 (Why is no real title available?)
• Exponentially more precise quantum simulation of fermions in second quantization
• How quantum is the speedup in adiabatic unstructured search?

This page was built for publication: Efficient discrete-time simulations of continuous-time quantum query algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5172735)