Qubit complexity of continuous problems

Anargyros Papageorgiou, Joseph F. Traub

Anargyros Papageorgiou, Joseph F. Traub

The number of qubits used by a quantum algorithm will be a crucial computational resource for the foreseeable future. We show how to obtain the classical query complexity for continuous problems. We then establish a simple formula for a lower bound on the qubit complexity in terms of the classical query complexity

Marco O. Lanzagorta, Jeffrey K. Uhlmann

Frank A. Wilczek, Hong-Ye Hu, Biao Wu

We present an algorithm for the generalized search problem (searching k marked items among N items) based on a continuous Hamiltonian and exploiting resonance. This resonant algorithm has the same time complexity O ( N / k ) as the Grover algorithm. A natural extension of the algorithm, incorporating auxiliary “monitor” qubits, can determine k precisely, if it is unknown. The time complexity of our counting algorithm is O ( N ) , similar to the best quantum approximate counting algorithm, or better, given appropriate physical resources.

Frank A. Wilczek, Wilczek, F, Biao Wu +3 more

© 2020 Chinese Physical Society and IOP Publishing Ltd. We present an algorithm for the generalized search problem (searching k marked items among N items) based on a continuous Hamiltonian and exploiting resonance. This resonant algorithm has the same time complexity as the Grover algorithm. A natural extension of the algorithm, incorporating auxiliary "monitor"qubits, can determine k precisely, if it is unknown. The time complexity of our counting algorithm is O(√N), similar to the best quantum approximate counting algorithm, or better, given appropriate physical resources.

Satoshi Iriyama, Makoto Ohya