The PRODSAT phase of random quantum satisfiability

• URL: http://arxiv.org/abs/2404.18447v1
• Date: Mon, 29 Apr 2024 06:10:45 GMT
• Title: The PRODSAT phase of random quantum satisfiability
• Abstract summary: 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.
• Score: 7.5465062534540515
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The $k$-QSAT problem is a quantum analog of the famous $k$-SAT constraint satisfaction problem. We must determine the zero energy ground states of a Hamiltonian of $N$ qubits consisting of a sum of $M$ random $k$-local rank-one projectors. 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. This means that the threshold of the PRODSAT phase is a purely geometric quantity equal to the dimer covering threshold. We revisit and fully prove this result through a combination of complex analysis and algebraic methods based on Buchberger's algorithm for complex polynomial equations with random coefficients. We also discuss numerical experiments investigating the presence of entanglement in the PRODSAT phase in the sense that product states do not span the whole zero energy ground state space.

Related papers

• Coherence-gated quantum devices via real-time weak measurement [0.0]
  Single-photon routers in cavity and circuit QED direct photons based on which eigenstate a qubit occupies.<n>We propose emphcoherence-gated routing, where the routing decision depends on the magnitude of quantum coherence.
  arXiv  Detail & Related papers  (2026-04-20T12:19:54Z)
• Search-Driven Clause Learning for Product-State Quantum $k$-SAT (PRODSAT-QSAT) [0.8301212911450326]
  We study PRODSAT-QSAT($k$): given rank-one $k$-local projectors, determine whether a quantum $k$-SAT instance admits a satisfying product state.<n>We formalise the problem, prove the soundness of the clause-learning rule, and describe a practical algorithm and implementation.
  arXiv  Detail & Related papers  (2026-03-20T15:22:27Z)
• Tight inapproximability of max-LINSAT and implications for decoded quantum interferometry [0.0]
  We prove by a direct reduction from Hstad's theorem that no-time algorithm can exceed the randomassignment ratio $r/q$ by any constant.<n>This threshold coincides with the $ell/m to 0$ limit of the semicircle law governing decoded quantum interferometry.
  arXiv  Detail & Related papers  (2026-03-04T19:26:26Z)
• On the Computational Complexity of Schrödinger Operators [6.1436827446807705]
  We study computational problems related to the Schr"odinger operator $H = -Delta + V$ in the real space. We prove that (i) simulating the dynamics generated by the Schr"odinger operator implements universal quantum computation, i.e., it is BQP-hard, and (ii) estimating the ground energy of the Schr"odinger operator is as hard as estimating that of local Hamiltonians with no sign problem (a.k.a. stoquastic Hamiltonians) This result is particularly intriguing because the ground energy problem for general bosonic Hamiltonians is known
  arXiv  Detail & Related papers  (2024-11-07T19:39:52Z)
• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  We prove that a simplified quantum Gibbs sampling algorithm achieves a $Omega(frac1k)$-fraction approximation of the optimum. Our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial.
  arXiv  Detail & Related papers  (2024-11-04T20:21:16Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Decomposing Hard SAT Instances with Metaheuristic Optimization [52.03315747221343]
  We introduce the notion of decomposition hardness (d-hardness) We show that the d-hardness expresses an estimate of the hardness of $C$ w.r.t.
  arXiv  Detail & Related papers  (2023-12-16T12:44:36Z)
• A hybrid Quantum proposal to deal with 3-SAT problem [75.38606213726906]
  This paper presents and describes a hybrid quantum computing strategy for solving 3-SAT problems. The performance of this approximation has been tested over a set of representative scenarios when dealing with 3-SAT from the quantum computing perspective.
  arXiv  Detail & Related papers  (2023-06-07T12:19:22Z)
• Testing quantum satisfiability [0.04297070083645048]
  We show that quantum k-SAT can be solved in randomised time. 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.
  arXiv  Detail & Related papers  (2023-01-25T17:02:46Z)
• The Parameterized Complexity of Quantum Verification [7.7155343772895275]
  We show that for the problem of quantum circuit satisfiability, there exists an algorithm solving the problem with a runtime scaling exponentially in the number of non-Clifford gates. We derive new lower bounds on the $T$-count of circuit satisfiability instances and the $$-count of the $W$-state.
  arXiv  Detail & Related papers  (2022-02-16T14:53:42Z)
• 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)
• K-sparse Pure State Tomography with Phase Estimation [1.2183405753834557]
  Quantum state tomography (QST) for reconstructing pure states requires exponentially increasing resources and measurements with the number of qubits. QST reconstruction for any pure state composed of the superposition of $K$ different computational basis states of $n$bits in a specific measurement set-up is presented.
  arXiv  Detail & Related papers  (2021-11-08T09:43:12Z)
• Annihilating Entanglement Between Cones [77.34726150561087]
  We show that Lorentz cones are the only cones with a symmetric base for which a certain stronger version of the resilience property is satisfied. Our proof exploits the symmetries of the Lorentz cones and applies two constructions resembling protocols for entanglement distillation.
  arXiv  Detail & Related papers  (2021-10-22T15:02:39Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings. In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$. We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
  arXiv  Detail & Related papers  (2020-02-25T19:18:36Z)
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates [0.0]
  We prove that $poly(t)cdot n1/D$-depth local random quantum circuits with two qudit nearest-neighbor gates are approximate $t$-designs in various measures. We also prove that anti-concentration is possible in depth O(log(n) loglog(n) using a different model.
  arXiv  Detail & Related papers  (2018-09-18T22:28:15Z)

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.