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/9702039

Tailoring Many-Body Interactions to Solve Hard Combinatorial Problems

Haiqing Wei, Xin Xue

Published Feb 20, 1997• 2 citations
arXivHTMLPDF

Abstract

A quantum machine consisting of interacting linear clusters of atoms is proposed for the 3SAT problem. Each cluster with two relevant states of collective motion can be used to register a Boolean variable. Given any 3SAT Boolean formula the interactions among the clusters can be so tailored that the ground state(s) (possibly degenerate) of the whole system encodes the satisfying truth assignment(s) for it. This relates the 3SAT problem to the dynamics of the properly designed glass system.

DOI
10.48550/arxiv.quant-ph/9702039

Related papers

A linear time quantum algorithm for 3SAT

Zachary B. Walters

A quantum algorithm for the NP complete problem of satisfying boolean formulas with three variables per clause (3SAT) is presented. Departing from traditional models of quantum computation, this algorithm makes extensive use of irreversible operations to incoherently transfer population from states which do not solve some problem of interest to states which do. Provided that a solution exists, the algorithm yields exponential decay of nonsolution probability, at a rate controlled by the user.

•Sep 29, 2015•0 citations

Static Quantum Computation

Haiqing Wei, Xin Xue

Tailoring many-body interactions among a proper quantum system endows it with computing ability by means of static quantum computation in the sense that some of the physical degrees of freedom can be used to store binary information and the corresponding binary variables satisfy some given logic relations if and only if the system is in the ground state. Two theorems are proved showing that the universal static quantum computer can encode the solutions for any P and NP problem into its ground state using only polynomial number (in the problem input size) of logic gates. The second step is to read out the solutions by relaxing the system. The time complexity is relevant when one tries to read out the solution by relaxing the system, therefore our model of static quantum computation provides a new connection between the computational complexity and the dynamics of a complex system.

arXiv:quant-ph/9702046•Feb 22, 1997•3 citations

Finding solutions to MaxSAT in a quantum computer

Leonardo Clemente, Salvador Elías Venegas-Andraca

Abstract We introduce a quantum algorithm designed to encode a 3-MaxSAT instance f(z) comprising n Boolean variables and m clauses. In the initial stage, we construct an unitary operator F ∈ SU(2n) whose corresponding eigenvalues are phase-encoded to reflect the total count of non-satisfiable clauses observed when evaluating f(z) under a truth assignment (a potential solution) ϕj . Our second stage consists in combining F along Quantum Phase Estimation to map the induced phase shifts into measurable quantum states in only O(mlog(m)) time due to commuting properties of F. Our objective is to identify a state |ϕj⟩ with the smallest phase shift induced by F. Such eigenstate |ϕj⟩ directly corresponds to the truth assignment minimizing the count of non-satisfiable clauses, thereby constituting our solution for f(z). We demonstrate how we can use this encoding along with Amplitude Amplification to find such solutions to MaxSAT in O(mlog(m)1.414n) time. In perspective, this search algorithm may represent an exponential speedup over MaxSAT algorithms, whose complexity grows exponentially as a function of the number of clauses.

•Jul 10, 2024•0 citations

Combinatorial Optimization with Coherent Ising Machines based on Degenerate Optical Parametric Oscillators

Y. Yamamoto

The basic concept, principle and implementation of coherent Ising machines are presented. A fully programmable 100 spin machine with all-to-all connections solves ground states and randomly samples low-energy excited states of NP-hard Ising problems.

Frontiers in Optics•Jan 1, 2016•0 citations

Superconductive Static Quantum Logic

Xin Xue, Haiqing Wei

Superconducting rings with exactly $Φ_0/2$ magnetic flux threading are analogous of Ising spins having two degenerate states which can be used to store binary information. When brought close these rings interact by means of magnetic coupling. If the interactions are properly tailored, a system of such superconducting rings can accomplish static quantum logic in the sense that the states of the rings interpreted as Boolean variables satisfy the desired logic relations when and only when the whole system is in the ground state. Such static logic is essential to carry out the static quantum computation [1,2].

arXiv:quant-ph/9702041•Feb 20, 1997•2 citations

Quantum simulation of a three-body-interaction Hamiltonian on an NMR quantum computer

Ching-Hsiang Tseng, Shyamal S. Somaroo, Yehuda Sharf +4 more

Extensions of average Hamiltonian theory to quantum computation permit the design of arbitrary Hamiltonians, allowing rotations throughout a large Hilbert space. In this way, the kinematics and dynamics of any quantum system may be simulated by a quantum computer. A basis mapping between the systems dictates the average Hamiltonian in the quantum computer needed to implement the desired Hamiltonian in the simulated system. The flexibility of the procedure is illustrated with NMR on ${}^{13}\mathrm{C}$ labeled alanine by creating the nonphysical Hamiltonian ${\ensuremath{\sigma}}_{z}{\ensuremath{\sigma}}_{z}{\ensuremath{\sigma}}_{z}$ corresponding to a three-body interaction.

arXiv:quant-ph/9908012•Physical Review A•Dec 10, 1999•129 citations
A quantum machine consisting of interacting linear clusters of atoms is proposed for the 3SAT problem. Each cluster with two relevant states of collective motion can be used to register a Boolean variable. Given any 3SAT Boolean formula the interactions among the clusters can be so tailored that the ground state(s) (possibly degenerate) of the whole system encodes the satisfying truth assignment(s) for it. This relates the 3SAT problem to the dynamics of the properly designed glass system.
Tailoring many-body interactions among a proper quantum system endows it with computing ability by means of static quantum computation in the sense that some of the physical degrees of freedom can be used to store binary information and the corresponding binary variables satisfy some given logic relations if and only if the system is in the ground state. Two theorems are proved showing that the universal static quantum computer can encode the solutions for any P and NP problem into its ground state using only polynomial number (in the problem input size) of logic gates. The second step is to read out the solutions by relaxing the system. The time complexity is relevant when one tries to read out the solution by relaxing the system, therefore our model of static quantum computation provides a new connection between the computational complexity and the dynamics of a complex system.
Abstract We introduce a quantum algorithm designed to encode a 3-MaxSAT instance f(z) comprising n Boolean variables and m clauses. In the initial stage, we construct an unitary operator F ∈ SU(2n) whose corresponding eigenvalues are phase-encoded to reflect the total count of non-satisfiable clauses observed when evaluating f(z) under a truth assignment (a potential solution) ϕj . Our second stage consists in combining F along Quantum Phase Estimation to map the induced phase shifts into measurable quantum states in only O(mlog(m)) time due to commuting properties of F. Our objective is to identify a state |ϕj⟩ with the smallest phase shift induced by F. Such eigenstate |ϕj⟩ directly corresponds to the truth assignment minimizing the count of non-satisfiable clauses, thereby constituting our solution for f(z). We demonstrate how we can use this encoding along with Amplitude Amplification to find such solutions to MaxSAT in O(mlog(m)1.414n) time. In perspective, this search algorithm may represent an exponential speedup over MaxSAT algorithms, whose complexity grows exponentially as a function of the number of clauses.
Superconducting rings with exactly Φ0/2Φ_0/2Φ0​/2 magnetic flux threading are analogous of Ising spins having two degenerate states which can be used to store binary information. When brought close these rings interact by means of magnetic coupling. If the interactions are properly tailored, a system of such superconducting rings can accomplish static quantum logic in the sense that the states of the rings interpreted as Boolean variables satisfy the desired logic relations when and only when the whole system is in the ground state. Such static logic is essential to carry out the static quantum computation [1,2].
Extensions of average Hamiltonian theory to quantum computation permit the design of arbitrary Hamiltonians, allowing rotations throughout a large Hilbert space. In this way, the kinematics and dynamics of any quantum system may be simulated by a quantum computer. A basis mapping between the systems dictates the average Hamiltonian in the quantum computer needed to implement the desired Hamiltonian in the simulated system. The flexibility of the procedure is illustrated with NMR on 13C{}^{13}\mathrm{C}13C labeled alanine by creating the nonphysical Hamiltonian ${\ensuremath{\sigma}}_{z}{\ensuremath{\sigma}}_{z}{\ensuremath{\sigma}}_{z}$ corresponding to a three-body interaction.