Search for: All records

Many important science and engineering problems can be converted into NP-complete problems which are of significant importance in computer science and mathematics. Currently, neither existing classical nor quantum algorithms can solve these problems in polynomial time. To address this difficulty, this paper proposes a quantum feasibility labeling (QFL) algorithm to label all possible solutions to the vertex coloring problem, which is a well-known NP-complete problem. The QFL algorithm converts the vertex coloring problem into the problem of searching an unstructured database where good and bad elements are labeled. The recently proposed variational quantum search (VQS) algorithm was demonstrated to achieve an exponential speedup, in circuit depth, up to 26 qubits in finding good element(s) from an unstructured database. Using the labels and the associated possible solutions as input, the VQS can find all feasible solutions to the vertex coloring problem. The number of qubits and the circuit depth required by the QFL each is a polynomial function of the number of vertices, the number of edges, and the number of colors of a vertex coloring problem. We have implemented the QFL on an IBM Qiskit simulator to solve a 4-colorable 4-vertex 3-edge coloring problem. 

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. 

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.