Testing quantum satisfiability

• URL: http://arxiv.org/abs/2301.10699v3
• Date: Fri, 13 Jun 2025 16:44:35 GMT
• Title: Testing quantum satisfiability
• Abstract summary: We show that quantum k-SAT can be solved in randomised time.<n>We first show that for a satisfiable instance of quantum k-SAT, most subproblems on a constant number of qubits are satisfiable by a product state.<n>We then show that for an instance of quantum k-SAT which is far from satisfiable by a product state, most subproblems are unsatisfiable by a product state.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum k-SAT (the problem of determining whether a k-local Hamiltonian is frustration-free) is known to be QMA_1-complete for k >= 3, and hence likely hard for quantum computers to solve. Building on a classical result of Alon and Shapira, we show that quantum k-SAT can be solved in randomised polynomial time given the `property testing' promise that the instance is either satisfiable (by any state) or far from satisfiable by a product state; by `far from satisfiable by a product state' we mean that \epsilon n^k constraints must be removed before a product state solution exists, for some fixed \epsilon > 0. The proof has two steps: we first show that for a satisfiable instance of quantum k-SAT, most subproblems on a constant number of qubits are satisfiable by a product state. We then show that for an instance of quantum k-SAT which is far from satisfiable by a product state, most subproblems are unsatisfiable by a product state. Given the promise, quantum k-SAT may therefore be solved by checking satisfiability by a product state on randomly chosen subsystems of constant size.

Related papers

• A Slice-Rank Drift Bound for Random Quantum \(k\)-SAT [0.0609170287691728]
  We prove a new upper bound on the satisfiability threshold of random quantum (k)-SAT.<n>The improvement is also significant at small values of (k), giving a bound of order (2k/k)<n>The proof combines the geometric formulation of generic quantum satisfiability with a dimension-decay analysis of the full satisfying subspace.
  arXiv  Detail & Related papers  (2026-07-26T21:18:02Z)
• Average-case quantum complexity from glassiness [45.57609001239456]
  Glassiness -- a phenomenon in physics characterized by a rough free-energy landscape -- implies hardness for stable classical algorithms.<n>We prove that the standard notion of quantum glassiness based on replica symmetry breaking obstructs stable quantum algorithms for Gibbs sampling.
  arXiv  Detail & Related papers  (2025-10-09T17:37:33Z)
• Quantum Counting in the Rydberg Blockade [0.0]
  We propose a quantum algorithm for counting the number of solutions to planar 2-satisfiability (2SAT) numerically on neutral atom quantum computers.<n>Our algorithm maps variables to atomic registers arranged in space according to a given formula, so that 2SAT constraints are enforced via the Rydberg blockade between neighboring atoms.
  arXiv  Detail & Related papers  (2025-06-24T04:09:55Z)
• The PRODSAT phase of random quantum satisfiability [7.5465062534540515]
  The $k$-QSAT problem is a quantum analog of the famous $k$-SAT constraint satisfaction problem. It is known that product states of zero energy exist with high probability if and only if the underlying factor graph has a clause-covering dimer configuration.
  arXiv  Detail & Related papers  (2024-04-29T06:10:45Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Complexity Classification of Product State Problems for Local Hamiltonians [0.94371657253557]
  We classify the complexity of finding minimum-energy product states for Hamiltonians defined by any fixed set of allowed 2-qubit interactions. We prove that estimating the minimum energy of a product state is in P if and only if all allowed interactions are 1-local, and NP-complete otherwise.
  arXiv  Detail & Related papers  (2024-01-12T17:51:09Z)
• Quantum Approximate Optimisation for Not-All-Equal SAT [9.427635404752936]
  We apply variational quantum algorithm QAOA to a variant of satisfiability problem (SAT): Not-All-Equal SAT. We show that while the runtime of both solvers scales exponentially with the problem size, the scaling for QAOA is smaller for large enough circuit depths.
  arXiv  Detail & Related papers  (2024-01-05T15:11:24Z)
• A Parallel and Distributed Quantum SAT Solver Based on Entanglement and Quantum Teleportation [1.5201992393140886]
  We develop a parallel quantum SAT solver, which reduces the time complexity in each iteration from linear time O(m) to constant time O(1) by utilising extra entangled qubits. We have proved the correctness of our approaches and demonstrated them in simulations.
  arXiv  Detail & Related papers  (2023-08-07T06:52:06Z)
• Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT [55.78588835407174]
  The amplitude amplification algorithm can be applied to unstructured search for satisfying variable assignments. The Quantum Approximate Optimization Algorithm (QAOA) is a promising candidate for solving 3SAT for Noisy Intermediate-Scale Quantum devices. We introduce amplitude amplification-inspired variants of QAOA to improve the success probability for 3SAT.
  arXiv  Detail & Related papers  (2023-03-02T11:52:39Z)
• Quantum Programming of the Satisfiability Problem with Rydberg Atom Graphs [1.2179548969182574]
  An experiment is presented to demonstrate the use of Rydberg atoms to solve (i.e., to program and obtain the solution of) the satisfiability (3-SAT) problem.
  arXiv  Detail & Related papers  (2023-02-28T07:49:10Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states. Our results open doors to the study of quantum algorithms in the average case.
  arXiv  Detail & Related papers  (2021-11-09T18:49:48Z)
• On the properties of the asymptotic incompatibility measure in multiparameter quantum estimation [62.997667081978825]
  Incompatibility (AI) is a measure which quantifies the difference between the Holevo and the SLD scalar bounds. We show that the maximum amount of AI is attainable only for quantum statistical models characterized by a purity larger than $mu_sf min = 1/(d-1)$.
  arXiv  Detail & Related papers  (2021-07-28T15:16:37Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Quantum algorithm of a set of quantum 2-sat problem [0.0]
  We present a quantum adiabatic algorithm for a set of quantum 2-satisfiability (Q2SAT) problem. For a Q2SAT problem, we construct the Hamiltonian which is similar to that of a Heisenberg chain.
  arXiv  Detail & Related papers  (2020-09-05T21:01:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.