Adiabatic oracle for Grover Algorithm

Speaker Name/Affiliation
Nikolay Sinitsyn / Los Alamos National Laboratory (LANL)
Seminar Type
Location (Room)
Duane Physics Room G126
Event Details & Abstracts

Conventional quantum algorithms use certain resources that are assumed to be given at almost no cost but are hard to provide in practice. An alternative is to work with “heuristic” approaches, such as DWave-like quantum annealing but there is no mathematical evidence that they work without similar “oracle”-like assumptions at some stage [1]. 

In this talk, I will argue that a practically useful and un-classically fast quantum computing is possible (on the edge of modern technology). Namely, I will describe a novel “hybrid” approach to hardware that realizes Grover’s oracle for numerous computational problems by means of quantum annealing in polynomial time, and realizes the search for a problem solution with the desired quantum speedup [2-3]. The proposed scheme should achieve quantum supremacy on computational problems using only ~60 qubits, without an access to a universal quantum gate set, and without the need for “all-to-all” qubit connectivity, and conventional quantum error correction.


[1] Bin Yan and NA Sinitsyn. Analytical solution for nonadiabatic quantum annealing to arbitrary Ising spin Hamiltonian. Nature Communications volume 13, Article number: 2212 (2022).

[2] Bin Yan and NA Sinitsyn. An adiabatic oracle for Grover's algorithm. arXiv/2207.05665. (submitted to Quantum)

[3] N. A. Sinitsyn and Bin Yan. “Topologically protected Grover's oracle for the Partition Problem”, Phys. Rev. A 108,022412 (2023)

Acknowledgment. This work was supported by the U.S. Department of Energy (DOE), Office of Science, Office of Advanced Scientific Computing Research, through the Quantum Internet to Accelerate Scientific Discovery Program