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

Artificial Life and Robotics

Study on discrete adiabatic quantum computation in 3-SAT problems

Mohamed El-fiky, Satoshi Ono, Shigeru Nakayama

Published Jun 1, 2011• 3 citations
Publisher
DOI
10.1007/s10015-011-0900-5

Related papers

Adiabatic quantum computing for random satisfiability problems

Tad Hogg

The discrete formulation of adiabatic quantum computing is compared with other search methods, classical and quantum, for random satisfiability (SAT) problems. With the number of steps growing only as the cube of the number of variables, the adiabatic method gives solution probabilities close to 1 for problem sizes feasible to evaluate via simulation on current computers. However, for these sizes the minimum energy gaps of most instances are fairly large, so the good performance scaling seen for small problems may not reflect asymptotic behavior where costs are dominated by tiny gaps. Moreover, the resulting search costs are much higher than for other methods. Variants of the quantum algorithm that do not match the adiabatic limit give lower costs, on average, and slower growth than the conventional GSAT heuristic method.

arXiv:quant-ph/0206059•Physical Review A•Feb 28, 2003•95 citations

A model of discrete quantum computation

Laura Gatti, Jesús García López de Lacalle

Quantum Information Processing•Jun 21, 2018•9 citations

On the Hamiltonian Operators for Adiabatic Quantum Reduction of SAT

William Cruz-Santos, Guillermo B. Morales-Luna

Lecture notes in computer science•Jan 1, 2010•2 citations

Study on discrete quantum adiabatic computation in combinatorial search problems

Mohamed El-fiky

The model of adiabatic quantum computation is a new paradigm for designing quantum algorithms. This model is based on the quantum adiabatic theorem, where a quantum computer evolves the quantum system slowly to switch gradually from an initial Hamiltonian with a ground state which is easy to construct, to a final Hamiltonian whose ground state encodes the solution of the problem to be solved. This dissertation presents an experimental study on the discrete quantum adiabatic computation in combinatorial search problems, we take k-Satisfiability problem as target problem to be examined. For k ? 3, k-SAT is NP-complete, i.e., among the most difficult NP problems in the worst case. Here we proposes a new monotonic variation method for the phase shift and mixing functions in the adiabatic quantum algorithm called the Quadric variation method, in order to speed up the algorithm search and decrease the overall resulting search cost. In addition, we present a better parameter configuration for the algorithm to be used with quadric variation as well as the previously proposed methods. The experiment are carried out in solving random instances of 3-SAT problems. The results indicate that the proposed method of using monotonic quadric variation in the phase functions of the adiabatic algorithm greatly improve the search behavior of the adiabatic algorithm and reduces the resulting search cost, also the results indicate that the better configuration of the algorithm parameters could greatly enhance the search behavior for the proposed method as well as the previously proposed methods.

•Jan 1, 2012•0 citations

Efficiency of structured adiabatic quantum computation

Juan José García‐Ripoll, Mari Carmen Bañuls

We show enough evidence that a structured version of Adiabatic Quantum Computation (AQC) is efficient for most satisfiability problems. More precisely, when the success probability is fixed beforehand, the computational resources grow subexponentially in the number of qubits. Our study focuses on random satisfiability and exact cover problems, developing a multi-step algorithm that solves clauses one by one. Relating the computational cost to classical properties of the problem, we collect significant statistics with up to N=140 qubits, around the phase transitions, which is where the hardest problems appear.

arXiv:0812.1760•Dec 9, 2008•2 citations

Quantum cooperative search algorithm for 3-SAT

Sheng-Tzong Cheng, Ming‐Hung Tao

Journal of Computer and System Sciences•Oct 20, 2006•17 citations
The discrete formulation of adiabatic quantum computing is compared with other search methods, classical and quantum, for random satisfiability (SAT) problems. With the number of steps growing only as the cube of the number of variables, the adiabatic method gives solution probabilities close to 1 for problem sizes feasible to evaluate via simulation on current computers. However, for these sizes the minimum energy gaps of most instances are fairly large, so the good performance scaling seen for small problems may not reflect asymptotic behavior where costs are dominated by tiny gaps. Moreover, the resulting search costs are much higher than for other methods. Variants of the quantum algorithm that do not match the adiabatic limit give lower costs, on average, and slower growth than the conventional GSAT heuristic method.
The model of adiabatic quantum computation is a new paradigm for designing quantum algorithms. This model is based on the quantum adiabatic theorem, where a quantum computer evolves the quantum system slowly to switch gradually from an initial Hamiltonian with a ground state which is easy to construct, to a final Hamiltonian whose ground state encodes the solution of the problem to be solved. This dissertation presents an experimental study on the discrete quantum adiabatic computation in combinatorial search problems, we take k-Satisfiability problem as target problem to be examined. For k ? 3, k-SAT is NP-complete, i.e., among the most difficult NP problems in the worst case. Here we proposes a new monotonic variation method for the phase shift and mixing functions in the adiabatic quantum algorithm called the Quadric variation method, in order to speed up the algorithm search and decrease the overall resulting search cost. In addition, we present a better parameter configuration for the algorithm to be used with quadric variation as well as the previously proposed methods. The experiment are carried out in solving random instances of 3-SAT problems. The results indicate that the proposed method of using monotonic quadric variation in the phase functions of the adiabatic algorithm greatly improve the search behavior of the adiabatic algorithm and reduces the resulting search cost, also the results indicate that the better configuration of the algorithm parameters could greatly enhance the search behavior for the proposed method as well as the previously proposed methods.
We show enough evidence that a structured version of Adiabatic Quantum Computation (AQC) is efficient for most satisfiability problems. More precisely, when the success probability is fixed beforehand, the computational resources grow subexponentially in the number of qubits. Our study focuses on random satisfiability and exact cover problems, developing a multi-step algorithm that solves clauses one by one. Relating the computational cost to classical properties of the problem, we collect significant statistics with up to N=140 qubits, around the phase transitions, which is where the hardest problems appear.