Abstract With the advent of powerful quantum computers, the quest for more efficient quantum algorithms becomes crucial in attaining quantum supremacy over classical counterparts in the noisy intermediate-scale quantum era. While Grover's search algorithm and its generalization, quantum amplitude amplification, offer quadratic speedup in solving various important scientific problems, their exponential time complexity limits scalability as the quantum circuit depths grow exponentially with the number of qubits. To overcome this challenge, we propose Variational Quantum Search (VQS), a novel algorithm based on variational quantum algorithms and parameterized quantum circuits. We show that a depth-10 Ansatz can amplify the total probability of k (k ≥ 1) good elements, out of 2n elements represented by n + 1 qubits, from k/2n 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. Our experimental results have validated the efficacy of VQS and its exponential advantage over Grover's algorithm in circuit depth for up to 26 qubits. We demonstrate that a depth-56 circuit in VQS can replace a depth-270,989 circuit in Grover's algorithm. Envisioning its potential, VQS holds promise to accelerate solutions to critical problems.
Abstract With the advent of powerful quantum computers, the quest for more efficient quantum algorithms becomes crucial in attaining quantum supremacy over classical counterparts in the noisy intermediate-scale quantum era. While Grover's search algorithm and its generalization, quantum amplitude amplification, offer quadratic speedup in solving various important scientific problems, their exponential time complexity limits scalability as the quantum circuit depths grow exponentially with the number of qubits. To overcome this challenge, we propose Variational Quantum Search (VQS), a novel algorithm based on variational quantum algorithms and parameterized quantum circuits. We show that a depth-10 Ansatz can amplify the total probability of k (k ≥ 1) good elements, out of 2n elements represented by n + 1 qubits, from k/2n 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. Our experimental results have validated the efficacy of VQS and its exponential advantage over Grover's algorithm in circuit depth for up to 26 qubits. We demonstrate that a depth-56 circuit in VQS can replace a depth-270,989 circuit in Grover's algorithm. Envisioning its potential, VQS holds promise to accelerate solutions to critical problems.
Abstract With powerful quantum computers already built1,2, we need more efficient quantum algorithms to achieve quantum supremacy over classical computers in the noisy intermediate-scale quantum (NISQ) era2,3. Grover's search algorithm4,5 and its generalization, quantum amplitude amplification6, provide quadratic speedup in solving many important scientific problems7. However, they still have exponential time complexity as the depths of their quantum circuits increase exponentially with the number of qubits6,7. To address this problem, we propose a new algorithm, Variational Quantum Search (VQS), which is based on the celebrated variational quantum algorithms8,9 and includes a parameterized quantum circuit, known as Ansatz. We show that a depth-10 Ansatz can amplify the total probability of k (k≥1) good elements, out of 2n elements represented by n+1 qubits, from k/2n 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.
Grover’s search algorithm (GSA) offers quadratic speedup in searching unstructured databases but suffers from exponential circuit depth complexity. Here, we present two quantum circuits called HX and Ry layers for the searching problem. Remarkably, both circuits maintain a fixed circuit depth of two and one, respectively, irrespective of the number of qubits used. When the target element’s position index is known, we prove that either circuit, combined with a single multi-controlled X gate, effectively amplifies the target element’s probability to over 0.99 for any qubit number greater than seven. To search unknown databases, we use the depth-1 Ry layer as the ansatz in the Variational Quantum Search (VQS), whose efficacy is validated through numerical experiments on databases with up to 26 qubits. The VQS with the Ry layer exhibits an exponential advantage, in circuit depth, over the GSA for databases of up to 26 qubits.
Grover's search algorithm is renowned for its dramatic speedup in solving many important scientific problems. The recently proposed Variational Quantum Search (VQS) algorithm has shown an exponential advantage over Grover's algorithm for up to 26 qubits. However, its advantage for larger numbers of qubits has not yet been proven. Here we show that the exponentially deep circuit required by Grover's algorithm can be replaced by a multi-controlled NOT gate together with either a single layer of Ry gates or two layers of circuits consisting of Hadamard and NOT gates, which is valid for any number of qubits greater than five. We prove that the VQS, with a single layer of Ry gates as its Ansatz, has near-perfect reachability in finding the good element of an arbitrarily large unstructured data set, and its reachability exponentially improves with the number of qubits, where the reachability is defined to quantify the ability of a given Ansatz to generate an optimal quantum state. Numerical studies further validate the excellent reachability of the VQS. Proving the near-perfect reachability of the VQS, with a depth-1 Ansatz, for any number of qubits completes an essential step in proving its exponential advantage over Grover's algorithm for any number of qubits, and the latter proving is significant as it means that the VQS can efficiently solve NP-complete problems.
Simulating quantum circuits using classical computers can accelerate the development and validation of quantum algorithms. Our newly developed algorithm, variational quantum search (VQS), has shown an exponential advantage over Grover's algorithm in the range from 5 to 26 qubits, in terms of circuit depth, for searching unstructured databases. We need to further validate the VQS for more than 26 qubits. Numerous simulators have been developed. However, it is not clear which simulator is most suitable for executing VQS with many qubits. To solve this issue, we implement a typical quantum circuit used in VQS on eight mainstream simulators. Results show that the time and memory required by most simulators increase exponentially with the number of qubits and that Pennylane with GPU and Qulacs are the most suitable simulators for executing VQS efficiently. Our results aid researchers in selecting suitable quantum simulators without the need for exhaustive implementation, and we have made our codes available for community contributions.
Variational quantum algorithms have become the de facto model for current quantum computations. A prominent example of such algorithms---the quantum approximate optimization algorithm (QAOA)---was originally designed for combinatorial optimization tasks, but has been shown to be successful for a variety of other problems. However, for most of these problems the optimal circuit depth remains unknown. One such problem is unstructured search, which consists of finding a particular bit string or, equivalently, preparing a state of high overlap with a target state. To bound the optimal QAOA depth for such a problem we build on its known solution in a continuous time quantum walk (CTQW). We Trotterize a CTQW to recover a QAOA sequence, and employ recent advances on the theory of Trotter formulas to bound the query complexity (circuit depth) needed to prepare a state that approaches perfect overlap with the target state. The obtained complexity exceeds Grover's algorithm complexity O(N21), but remains smaller than O(N21+c) for any c>0, which shows quantum advantage of QAOA over classical solutions. We verify our analytical predictions by numerical simulations of up to 68 qubits.
Grover search is a renowned quantum search algorithm that leverages quantum superposition to find a marked item with quadratic speedup. However, when implemented on Noisy Intermediate-scale Quantum (NISQ) hardware, the required repeated iterations of the oracle and diffusion operators increase exponentially with the number of qubits, resulting in significant noise accumulation. To address this, we propose a hybrid quantum-classical architecture that replaces quantum iterations with updates from a classical optimizer. This optimizer minimizes the expectation value of an oracle Hamiltonian with respect to a parameterized quantum state representing the target bit string. Our parameterized quantum circuit is much shallower than Grover search circuit, and we found that it outperforms Grover search on noisy simulators and NISQ hardware. When the number of qubits is greater than 5, our approach still maintains usable success probability, while the success probability of Grover search is at the same level as random guessing.