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.
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.
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.
The increasing complexity of quantum algorithms and the limitations of current Noisy Intermediate-Scale Quantum (NISQ) hardware underscore the importance of efficient classical simulators. To support informed decision-making by users of quantum circuit simulators, we benchmark seven statevector-based quantum circuit simulators (Qiskit, Qulacs, Qibo, Qsimov, Cirq, Pennylane and the Intel Quantum Simulator (IQS)) on a multicore node of the Lusitania high-performance computing (HPC) system. We evaluate their performance in terms of execution time, memory usage and core scalability using Grover’s algorithm, the quantum Fourier transform (QFT), and quantum volume (QV) circuits, across qubit counts ranging from 3 to 30. Our results reveal that Qulacs offers the best performance for circuits below 22 qubits, while Qiskit becomes the fastest for larger and more complex circuits. Qiskit and Qulacs achieve the most efficient parallel performance across multiple cores, while others display limited scaling benefits. IQS shows the lowest memory consumption in QFT and QV benchmarks for systems under 24 qubits; however, it suffers from higher execution times, particularly for Grover’s algorithm. The experimental implementation of Qsimov consistently underperforms in both runtime and scalability; for this reason, it is employed as a baseline in our measurements, serving to highlight the importance of performance optimizations in statevector-based quantum circuit simulators. Previous findings provide a comprehensive performance landscape to guide researchers in selecting appropriate simulators for both standard and large-scale quantum workloads on HPC infrastructures.
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.
In the nearest future quantum computers will be suitable for practical use. The development of quantum algorithms can be carried out using classical computers and specialized software that allows simulating of a quantum circuit functioning. Simulation results can be used to analyze the algorithm and also contribute to co-design when developing quantum architectures. However, when planning and performing numerical experiments, it is necessary to understand the capabilities of simulators and the limitations on the parameters of the quantum circuit imposed by the characteristics of the available classical computational resources (computers). This paper presents the results of computational experiments on simulating the operation of quantum circuits on an ideal quantum computer using the QuEST and Intel-QS packages, as well as our own "naïve" implementation. Restrictions on the size of a simulated quantum system N are shown when using computing systems of various classes — a virtual machine, a computing server, a computing server with a graphics accelerator (GPU), a supercomputer (the maximum achieved size is N = 33). The performance and scalability characteristics of the considered implementations on shared and distributed memory are given (the observed scaling efficiency is 30 % and 70 %, respectively). For the QuEST package and our own implementation the performance is presented for systems with graphics accelerator (GPU).
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.