Efficient quantum algorithm for solving structured problems via multi-step quantum computation
arXiv:1912.06959 · doi:10.1103/PhysRevResearch.5.L012004
Abstract
In classical computation, a problem can be solved in multiple steps where calculated results of each step can be copied and used repeatedly. While in quantum computation, it is difficult to realize a similar multi-step computation process because the no-cloning theorem forbids making copies of an unknown quantum state perfectly. We find a method based on quantum resonant transition to protect and reuse an unknown quantum state that encodes calculated results of an intermediate step without making copies of the state, and present a quantum algorithm that solves a problem via a multi-step quantum computation process. This algorithm can achieve an exponential speedup over classical algorithms in solving a type of structured search problems.
arXiv comment36 pages, 4 figures, paper is re-formulated, more details are added
References in corpus (15)
- Quantum Mechanics helps in searching for a needle in a haystack
- Adiabatic Quantum Computing
- Hamiltonian Simulation by Qubitization
- A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors
- Optimal Hamiltonian Simulation by Quantum Signal Processing
- Quantum Search by Local Adiabatic Evolution
- Realization of a scalable Shor algorithm
- Preparing ground states of quantum many-body systems on a quantum computer
- Quantum Algorithm for Spectral Measurement with Lower Gate Count
- Nested quantum search and NP-complete problems
- Quantum search by measurement
- Quantum Simulation of Resonant Transitions for Solving the Eigen-problem of an Effective Water Hamiltonian
- The Power of Adiabatic Quantum Computation with No Sign Problem
- Adiabatic quantum search algorithm for structured problems
- Quantum algorithm for obtaining the eigenstates of a physical system