4 papers
Quadratic Sums-of-Powers for Fixed-Parameter Tractable Quantum-Circuit Simulation
Alexis de Colnet, Floris Geerts, Rihan Hai +4
Strongly simulating a quantum circuit, that is, computing an output amplitude, can be done by summing the circuit's Feynman paths: a weighted count over assignments to Boolean path…
The Compilability Thresholds of 2-CNF to OBDD
Alexis de Colnet, Alfons Laarman, Joon Hyung Lee
We prove the existence of two thresholds regarding the compilability of random 2-CNF formulas to OBDDs. The formulas are drawn from , the uniform distribution…
Search-Driven Clause Learning for Product-State Quantum -SAT (PRODSAT-QSAT)
Samuel González-Castillo, Joon Hyung Lee, Alfons Laarman
We study PRODSAT-QSAT(): given rank-one -local projectors, determine whether a quantum -SAT instance admits a satisfying product state. We present a CDCL-style refutation…
The PRODSAT phase of random quantum satisfiability
Joon Lee, Nicolas Macris, Jean Bernoulli Ravelomanana +1
The -QSAT problem is a quantum analog of the famous -SAT constraint satisfaction problem. We must determine the zero energy ground states of a Hamiltonian of qubits consi…