On the satisfiability of quantum circuits of small treewidth

DOI10.1007/s00224-016-9727-8zbMath1378.68044OpenAlexW1936478157MaRDI QIDQ2411047

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 computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Satisfiability, branch-width and Tseitin tautologies
• Graph minors. III. Planar tree-width
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Graph minors. XIII: The disjoint paths problem
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• On exact algorithms for treewidth
• Quantum Computation and Quantum Information
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• On the Satisfiability of Quantum Circuits of Small Treewidth
• Easy problems for tree-decomposable graphs
• Complexity and Algorithms for Well-Structured k-SAT Instances
• Simulating Quantum Computation by Contracting Tensor Networks
• Bounded Round Interactive Proofs in Finite Groups
• On the role of entanglement in quantum-computational speed-up
• Theory and Applications of Satisfiability Testing
• On the complexity of \(k\)-SAT