Finding Solutions to the Integer Case Constraint Satisfiability Problem Using Grover’s Algorithm

Finding Solutions to the Integer Case Constraint Satisfiability Problem Using Grover’s Algorithm

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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Gayathree M. Vinod, Anil Shaji
Formato: article
Lenguaje:EN
Publicado: IEEE 2021
Materias:
Constraint satisfiability
Grover’s algorithm
noisy intermediate-scale quantum (NISQ) processors
Qiskit
Atomic physics. Constitution and properties of matter
QC170-197
Materials of engineering and construction. Mechanics of materials
TA401-492
Acceso en línea:https://doaj.org/article/a6327c7a264b499dadea46761667f1b3
Etiquetas: Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
id oai:doaj.org-article:a6327c7a264b499dadea46761667f1b3
record_format dspace
spelling oai:doaj.org-article:a6327c7a264b499dadea46761667f1b32021-11-20T00:03:13ZFinding Solutions to the Integer Case Constraint Satisfiability Problem Using Grover’s Algorithm2689-180810.1109/TQE.2021.3120449https://doaj.org/article/a6327c7a264b499dadea46761667f1b32021-01-01T00:00:00Zhttps://ieeexplore.ieee.org/document/9576649/https://doaj.org/toc/2689-1808Constraint 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 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.Gayathree M. VinodAnil ShajiIEEEarticleConstraint satisfiabilityGrover’s algorithmnoisy intermediate-scale quantum (NISQ) processorsQiskitAtomic physics. Constitution and properties of matterQC170-197Materials of engineering and construction. Mechanics of materialsTA401-492ENIEEE Transactions on Quantum Engineering, Vol 2, Pp 1-13 (2021)
institution DOAJ
collection DOAJ
language EN
topic Constraint satisfiability
Grover’s algorithm
noisy intermediate-scale quantum (NISQ) processors
Qiskit
Atomic physics. Constitution and properties of matter
QC170-197
Materials of engineering and construction. Mechanics of materials
TA401-492
spellingShingle Constraint satisfiability
Grover’s algorithm
noisy intermediate-scale quantum (NISQ) processors
Qiskit
Atomic physics. Constitution and properties of matter
QC170-197
Materials of engineering and construction. Mechanics of materials
TA401-492
Gayathree M. Vinod
Anil Shaji
Finding Solutions to the Integer Case Constraint Satisfiability Problem Using Grover’s Algorithm
description 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 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.
format article
author Gayathree M. Vinod
Anil Shaji
author_facet Gayathree M. Vinod
Anil Shaji
author_sort Gayathree M. Vinod
title Finding Solutions to the Integer Case Constraint Satisfiability Problem Using Grover’s Algorithm
title_short Finding Solutions to the Integer Case Constraint Satisfiability Problem Using Grover’s Algorithm
title_full Finding Solutions to the Integer Case Constraint Satisfiability Problem Using Grover’s Algorithm
title_fullStr Finding Solutions to the Integer Case Constraint Satisfiability Problem Using Grover’s Algorithm
title_full_unstemmed Finding Solutions to the Integer Case Constraint Satisfiability Problem Using Grover’s Algorithm
title_sort finding solutions to the integer case constraint satisfiability problem using grover’s algorithm
publisher IEEE
publishDate 2021
url https://doaj.org/article/a6327c7a264b499dadea46761667f1b3
work_keys_str_mv AT gayathreemvinod findingsolutionstotheintegercaseconstraintsatisfiabilityproblemusinggroverx2019salgorithm
AT anilshaji findingsolutionstotheintegercaseconstraintsatisfiabilityproblemusinggroverx2019salgorithm
_version_ 1718419855162474496

Ejemplares similares