Topologically protected Grover's oracle for the partition problem

Abstract

The Number Partitioning Problem (NPP) is one of the NP-complete computational problems. Its definite exact solution generally requires a check of all $N$ solution candidates, which is exponentially large. Here we describe a path to the fast solution of this problem in $\sqrt{N}$ quasi-adiabatic quantum annealing steps. We argue that the errors due to the finite duration of the quantum annealing can be suppressed if the annealing time scales with $N$ only logarithmically. Moreover, our adiabatic oracle is topologically protected, in the sense that it is robust against small uncertainty and slow time-dependence of the physical parameters or the choice of the annealing protocol.

v2: final version; to appear in Physical Review A

References in corpus (6)

• Quantum algorithm for solving linear systems of equations
• High-fidelity preparation, gates, memory and readout of a trapped-ion quantum bit
• Adiabatic approximation with exponential accuracy for many-body systems and quantum computation
• Efficient Fully-Coherent Quantum Signal Processing Algorithms for Real-Time Dynamics Simulation
• Number Partitioning with Grover's Algorithm in Central Spin Systems
• Analytical solution for nonadiabatic quantum annealing to arbitrary Ising spin Hamiltonian

Cited by in corpus (1)

• Quantum mutual information redistribution by Number Partitioning algorithm