On the satisfiability of quantum circuits of small treewidth

DOI10.1007/S00224-016-9727-8MaRDI QIDQ2411047zbMATH OpenOpenAlexFDO

Authors Mateus de Oliveira Oliveira

Publication date 20 October 2017

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-016-9727-8

zbMATH Keywords

treewidthtensor networksMerlin-Arthur protocolssatisfiability of quantum circuits

Mathematics Subject Classification ID

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

Recommendations

• On the satisfiability of quantum circuits of small treewidth
• A near-quadratic lower bound for the size of quantum circuits of constant treewidth
• Simulating Quantum Computation by Contracting Tensor Networks
• NP vs QMA\(_{\log}(2)\)
• Quantum 3-SAT Is QMA\(_1\)-complete

Cites work

• 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?)
• scientific article; zbMATH DE number 4121424 (Why is no real title available?)
• 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
• Graph minors. XIII: The disjoint paths problem
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• On exact algorithms for treewidth
• On the complexity of \(k\)-SAT
• On the role of entanglement in quantum-computational speed-up
• On the satisfiability of quantum circuits of small treewidth
• 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)

• A near-quadratic lower bound for the size of quantum circuits of constant treewidth
• On the power of a unique quantum witness
• Entropy lower bounds for quantum decision tree complexity
• Simulating Quantum Computation by Contracting Tensor Networks
• SAT-based {CNOT, \(T\)} quantum circuit synthesis
• On the satisfiability of quantum circuits of small 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 Q2411047)