Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0309077

A Constant Complexity Algorithm for Solving the Boolean Satisfiability Problem on Quantum Computers

Ahmed Younes, Julian F. Miller

Published Sep 9, 2003• 0 citations
arXivHTMLPDF

Abstract

This paper has been withdrawn by the author(s). Please refer to quant-ph/0311171.
DOI
10.48550/arxiv.quant-ph/0309077

Related papers

Quantum Bit Commitment from a Computation Bound

Adrian Kent

This paper is withdrawn. See quant-ph/9806031 for a discussion.

arXiv:quant-ph/9711069•Nov 26, 1997•3 citations

An Exponentially Fast Quantum Search Algorithm

Goong Chen, Zijian Diao

This paper has been withdrawn by the authors.

arXiv:quant-ph/0011109•Nov 27, 2000•13 citations

Quantum 3-SAT Is QMA$_1$-Complete

David Gosset, Daniel Nagaj

Quantum satisfiability is a constraint satisfaction problem that generalizes classical boolean satisfiability. In the quantum $k$-SAT problem, each constraint is specified by a $k$-local projector and is satisfied by any state in its nullspace. Bravyi showed that quantum 2-SAT can be solved efficiently on a classical computer and that quantum $k$-SAT with $k\geq 4$ is QMA$_1$-complete [S. Bravyi, Efficient Algorithm for a Quantum Analogue of 2-SAT, eprint arXiv:quant-ph/0602108, 2006]. Quantum 3-SAT was known to be contained in QMA$_1$ [Bravyi, 2006], but its computational hardness was unknown until now. We prove that quantum 3-SAT is QMA$_1$-hard, and therefore complete for this complexity class.

SIAM Journal on Computing•Jan 1, 2016•16 citations

A Formalism for Quantum Computing and a Satisfiability Problem

César Bautista-Ramos, M. Castro-Cardona, Alfred Zehe

Elsevier eBooks•Jan 1, 2005•0 citations

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

Diogo Fernandes, Inês Dutra

column Using Grover's search quantum algorithm to solve Boolean satisfiability problems: Part I Share on Authors: Diogo Fernandes University of Porto, Portugal University of Porto, PortugalView Profile , Inês Dutra University of Porto, Portugal University of Porto, PortugalView Profile Authors Info & Affiliations XRDS: Crossroads, The ACM Magazine for StudentsVolume 26Issue 1Fall 2019 pp 64–66https://doi.org/10.1145/3358251Published:17 September 2019 0citation289DownloadsMetricsTotal Citations0Total Downloads289Last 12 Months67Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

XRDS Crossroads The ACM Magazine for Students•Sep 17, 2019•7 citations

On the Complexity of Searching for a Maximum of a Function on a Quantum Computer

Maciej Goćwin

arXiv:quant-ph/0507060•Quantum Information Processing•Feb 1, 2006•6 citations
Quantum 3-SAT Is QMA1_11​-Complete
Quantum satisfiability is a constraint satisfaction problem that generalizes classical boolean satisfiability. In the quantum kkk-SAT problem, each constraint is specified by a kkk-local projector and is satisfied by any state in its nullspace. Bravyi showed that quantum 2-SAT can be solved efficiently on a classical computer and that quantum kkk-SAT with k≥4k\geq 4k≥4 is QMA1_11​-complete [S. Bravyi, Efficient Algorithm for a Quantum Analogue of 2-SAT, eprint arXiv:quant-ph/0602108, 2006]. Quantum 3-SAT was known to be contained in QMA1_11​ [Bravyi, 2006], but its computational hardness was unknown until now. We prove that quantum 3-SAT is QMA1_11​-hard, and therefore complete for this complexity class.
column Using Grover's search quantum algorithm to solve Boolean satisfiability problems: Part I Share on Authors: Diogo Fernandes University of Porto, Portugal University of Porto, PortugalView Profile , Inês Dutra University of Porto, Portugal University of Porto, PortugalView Profile Authors Info & Affiliations XRDS: Crossroads, The ACM Magazine for StudentsVolume 26Issue 1Fall 2019 pp 64–66https://doi.org/10.1145/3358251Published:17 September 2019 0citation289DownloadsMetricsTotal Citations0Total Downloads289Last 12 Months67Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access