Finding solutions to the integer case constraint satisfiability problem using Grover's algorithm
arXiv:2106.09976 · doi:10.1109/TQE.2021.3120449
Abstract
Constraint satisfiability problems, crucial to several applications, are solved on a quantum computer using Grover's search algorithm, leading to a quadratic improvement over the classical case. The solutions are obtained with high probability for several cases and are illustrated for the cases involving two variables for both 3- and 4-bit numbers. Methods are defined for inequality comparisons, and these are combined according to the form of the satisfiability formula, to form the oracle for the algorithm. The circuit is constructed using IBM Qiskit and is verified on an IBM simulator. It is further executed on one of the Noisy Intermediate-Scale Quantum (NISQ) processors from IBM on the cloud. Noise levels in the processor at present are found to be too high for successful execution. Running the algorithm on the simulator with a custom noise model lets us identify the noise threshold for successful execution.
arXiv comment13 pages, 12 figures
References in corpus (12)
- Quantum Computing in the NISQ era and beyond
- Quantum Mechanics helps in searching for a needle in a haystack
- Elementary gates for quantum computation
- Validating quantum computers using randomized model circuits
- Synthesis and Optimization of Reversible Circuits - A Survey
- Quantum circuits of T-depth one
- On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization
- Quantum Gates and Circuits
- Linear-Depth Quantum Circuits for n-qubit Toffoli gates with no Ancilla
- New techniques for fault-tolerant decomposition of Multi-Controlled Toffoli gate
- Subdivided Phase Oracle for NISQ Search Algorithms
- Solving mathematical problems with quantum search algorithm