Variational Quantum Search with Exponential Speedup

With powerful quantum computers already built, we need more efficient quantum algorithms to achieve quantum supremacy over classical computers in the noisy intermediate-scale quantum (NISQ) era. Grover's search algorithm and its generalization, quantum amplitude amplification, provide quadratic speedup in solving many important scientific problems. However, they still have exponential time complexity as the depths of their quantum circuits increase exponentially with the number of qubits. To address this problem, we propose a new algorithm, Variational Quantum Search (VQS), which is based on the celebrated variational quantum algorithms and includes a parameterized quantum circuit, known as Ansatz. We show that a depth-10 Ansatz can amplify the total probability of $k$ ($k \geq 1$) good elements, out of $2^n$ elements represented by $n$+1 qubits, from $k/2^n$ to nearly 1, as verified for $n$ up to 26, and that the maximum depth of quantum circuits in the VQS increases linearly with the number of qubits. We demonstrate that a depth-56 circuit in VQS can replace a depth-270,989 circuit in Grover's algorithm, and thus VQS is more suitable for NISQ computers. We envisage our VQS could exponentially speed up the solutions to many important problems, including the NP-complete problems, which is widely considered impossible.