On the satisfiability of quantum circuits of small treewidth

DOI10.1007/978-3-319-20297-6_11MaRDI QIDQ3194714zbMATH OpenOpenAlexFDO

Authors Mateus de Oliveira Oliveira

Publication date 20 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.5565

zbMATH Keywords

satisfiability of quantum circuitstensor networkstreewidth

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Abstract: It has been known for almost three decades that many $mathrmNP$-hard optimization problems can be solved in polynomial time when restricted to structures of constant treewidth. In this work we provide the first extension of such results to the quantum setting. We show that given a quantum circuit $C$ with $n$ uninitialized inputs, $mathitpoly(n)$ gates, and treewidth $t$, one can compute in time $(fracndelta{)}^{exp(O(t))}$ a classical assignment $yin{0,1}^n$ that maximizes the acceptance probability of $C$ up to a $delta$ additive factor. In particular, our algorithm runs in polynomial time if $t$ is constant and $1/poly(n)<delta<1$. For unrestricted values of $t$, this problem is known to be complete for the complexity class $mathrmQCMA$, a quantum generalization of MA. In contrast, we show that the same problem is $mathrmNP$-complete if $t=O(logn)$ even when $delta$ is constant. On the other hand, we show that given a $n$-input quantum circuit $C$ of treewidth $t=O(logn)$, and a constant $delta<1/2$, it is $mathrmQMA$-complete to determine whether there exists a quantum state $mid!varphianglein(mathbb{C}^d{)}^{otimesn}$ such that the acceptance probability of $Cmid!varphiangle$ is greater than $1-delta$, or whether for every such state $mid!varphiangle$, the acceptance probability of $Cmid!varphiangle$ is less than $delta$. As a consequence, under the widely believed assumption that $mathrmQMAeqmathrmNP$, we have that quantum witnesses are strictly more powerful than classical witnesses with respect to Merlin-Arthur protocols in which the verifier is a quantum circuit of logarithmic treewidth.

Recommendations

• On the satisfiability of quantum circuits of small treewidth
• A near-quadratic lower bound for the size of quantum circuits of constant treewidth
• Beating brute force for (quantified) satisfiability of circuits of bounded treewidth
• Simulating Quantum Computation by Contracting Tensor Networks
• Quantum 3-SAT Is QMA₁-complete

Cites work

• Bounded Round Interactive Proofs in Finite Groups
• Complexity and Algorithms for Well-Structured k-SAT Instances
• Easy problems for tree-decomposable graphs
• Graph minors. III. Planar tree-width
• scientific article; zbMATH DE number 2080246 (Why is no real title available?)
• scientific article; zbMATH DE number 1775384 (Why is no real title available?)
• scientific article; zbMATH DE number 1776257 (Why is no real title available?)
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• On the role of entanglement in quantum-computational speed-up
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Quantum computation and quantum information. 10th anniversary edition
• Satisfiability, branch-width and Tseitin tautologies
• Simulating Quantum Computation by Contracting Tensor Networks
• The Heisenberg representation of quantum computers
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Theory and Applications of Satisfiability Testing
• Width-parametrized SAT: time-space tradeoffs

Cited in

(6)

• SAT-based {CNOT, \(T\)} quantum circuit synthesis
• Entropy lower bounds for quantum decision tree complexity
• On the satisfiability of quantum circuits of small treewidth
• Simulating Quantum Computation by Contracting Tensor Networks
• A near-quadratic lower bound for the size of quantum circuits of constant treewidth
• Beating brute force for (quantified) satisfiability of circuits of bounded treewidth

This page was built for publication: On the satisfiability of quantum circuits of small treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3194714)