Mitchell Institute for Fundamental Physics & Astronomy
College Station, Texas 77843
Quantum algorithms, such as by Shor and Grover, rely on the concept of an oracle, which is a quantum function that can be called by a computer in one computation step. In real applications this function is not given for free. It must be generated as a quantum dynamic process. It may be harder to realize than to solve the original problem. I will argue that a physical solution for the fast oracle implementation for many famous NP-complete problems is possible. Moreover, this may be easier to implement in practice than the universal quantum computing.
References Bin Yan, and N. A. Sinitsyn. Adiabatic oracle for Grover algorithm. arXiv:2207.05665  Bin Yan, and N. A. Sinitsyn. Analytical solution for nonadiabatic quantum annealing to arbitrary Ising spin Hamiltonian. Nature Comm. 13 (1): 2212 (2022)