column

Using Grover's search quantum algorithm to solve Boolean satisfiability problems: Part I

Authors:

Diogo Fernandes,

Inês DutraAuthors Info & Claims

XRDS: Crossroads, The ACM Magazine for Students, Volume 26, Issue 1

Pages 64 - 66

https://doi.org/10.1145/3358251

Published: 17 September 2019 Publication History

Get Access

References

[1]

Cook, S. A. The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing, ACM, 2971.

Digital Library

Google Scholar

[2]

Biere, A., Heule, M., Maaren, H. v., and Walsh, T. Handbook of Satisfiability: Volume 185 Frontiers in Artificial Intelligence and Applications. IOS Press Amsterdam, The Netherlands, 2009.

Digital Library

Google Scholar

[3]

Nielsen, M.A. and Chuang, I. Quantum computation and quantum information. American Journal of Physics 70, 558 (2002).

Crossref

Google Scholar

[4]

Dirac, P. A. M. A new notation for quantum mechanics. Mathematical Proceedings of the Cambridge Philosophical Society 5, 3 (1939).

Google Scholar

[5]

Vedral, V. and Plenio M.B. Basics of quantum computation. Progress in Quantum Electronics 22, 1 (1998), 1--9.

Crossref

Google Scholar

[6]

Ambainis, A. Quantum search algorithms. ACM SIGACT News 3, 2 (2004), 2--35.

Digital Library

Google Scholar

[7]

IBM Research IQT. Grover's Algorithm (2017); https://quantumexperience.ng.bluemix.net/proxy/tutorial/full-user-guide/004-Quantum_Algorithms/070-Grover%27s_Algorithm.html.

Google Scholar

[8]

Strubell, E. An introduction to quantum algorithms. COS498 Chawa the Spring. 2011; http://mmrc.amss.cas.cn/tlb/201702/W020170224608150507023.pdf.

Google Scholar

[9]

Grover, L. K. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, ACM, 1996.

Digital Library

Google Scholar

Cited By

View all

Jiang JWang Y(2024)Using a Simplified Quantum Counter to Implement Quantum Circuits Based on Grover’s Algorithm to Tackle the Exact Cover ProblemMathematics10.3390/math1301009013:1(90)Online publication date: 29-Dec-2024
https://doi.org/10.3390/math13010090
Lin SWang TChen YHou ZSanán DTeo Y(2024)A Parallel and Distributed Quantum SAT Solver Based on Entanglement and TeleportationTools and Algorithms for the Construction and Analysis of Systems10.1007/978-3-031-57249-4_18(363-382)Online publication date: 5-Apr-2024
https://doi.org/10.1007/978-3-031-57249-4_18
Varmantchaonala CFendji JNjafa JAtemkeng M(2023)Quantum hybrid algorithm for solving SAT problemEngineering Applications of Artificial Intelligence10.1016/j.engappai.2023.106058121(106058)Online publication date: May-2023
https://doi.org/10.1016/j.engappai.2023.106058
Show More Cited By

Index Terms

Using Grover's search quantum algorithm to solve Boolean satisfiability problems: Part I
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques

Recommendations

Using Grover's search quantum algorithm to solve Boolean satisfiability problems, part 2
Global Cultures and Computing
Three-qubit Grover's algorithm using superconducting quantum interference devices in cavity-QED

We present a scheme for the implementation of three-qubit Grover's algorithm using four-level superconducting quantum interference devices (SQUIDs) coupled to a superconducting resonator. The scheme is based on resonant, off-resonant interaction of the ...
A satisfiability procedure for quantified boolean formulae
The renesse issue on satisfiability

We present a satisfiability tester QSAT for quantified Boolean formulae and a restriction QSAT_CNF of QSAT to unquantified conjunctive normal form formulae. QSAT makes use of procedures which replace subformulae of a formula by equivalent formulae. By a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image XRDS: Crossroads, The ACM Magazine for Students

XRDS: Crossroads, The ACM Magazine for Students Volume 26, Issue 1

The Future of Devices

Fall 2019

62 pages

ISSN:1528-4972

EISSN:1528-4980

DOI:10.1145/3363438

Editors:
Diane Golay
Uppsala University, Sweden
,
Gierad Laput
Carnegie Mellon University

Issue’s Table of Contents

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 September 2019

Published in XRDS Volume 26, Issue 1

Check for updates

Qualifiers

Column
Popular
Un-reviewed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
453
Total Downloads

Downloads (Last 12 months)34
Downloads (Last 6 weeks)7

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Jiang JWang Y(2024)Using a Simplified Quantum Counter to Implement Quantum Circuits Based on Grover’s Algorithm to Tackle the Exact Cover ProblemMathematics10.3390/math1301009013:1(90)Online publication date: 29-Dec-2024
https://doi.org/10.3390/math13010090
Lin SWang TChen YHou ZSanán DTeo Y(2024)A Parallel and Distributed Quantum SAT Solver Based on Entanglement and TeleportationTools and Algorithms for the Construction and Analysis of Systems10.1007/978-3-031-57249-4_18(363-382)Online publication date: 5-Apr-2024
https://doi.org/10.1007/978-3-031-57249-4_18
Varmantchaonala CFendji JNjafa JAtemkeng M(2023)Quantum hybrid algorithm for solving SAT problemEngineering Applications of Artificial Intelligence10.1016/j.engappai.2023.106058121(106058)Online publication date: May-2023
https://doi.org/10.1016/j.engappai.2023.106058
Roch CLondono Castillo SLinnhoff-Popien C(2022)A Grover based Quantum Algorithm for Finding Pure Nash Equilibria in Graphical Games2022 IEEE 19th International Conference on Software Architecture Companion (ICSA-C)10.1109/ICSA-C54293.2022.00036(147-151)Online publication date: Mar-2022
https://doi.org/10.1109/ICSA-C54293.2022.00036

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Digital Edition

View this article in digital edition.

Digital Edition

Magazine Site

View this article on the magazine site (external)

Magazine Site

References

Cited By

Index Terms

Recommendations

Using Grover's search quantum algorithm to solve Boolean satisfiability problems, part 2

Three-qubit Grover's algorithm using superconducting quantum interference devices in cavity-QED

A satisfiability procedure for quantified boolean formulae

Comments

Information

Published In

Publisher

Publication History

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Digital Edition

Magazine Site

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations