On the satisfiability of quantum circuits of small treewidth

DOI10.1007/S00224-016-9727-8zbMATH Open1378.68044OpenAlexW1936478157MaRDI QIDQ2411047FDOQ2411047

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

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

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)

Cites Work

• On exact algorithms for treewidth
• Graph minors. XIII: The disjoint paths problem
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The Heisenberg representation of quantum computers
• Quantum computation and quantum information. 10th anniversary edition
• Easy problems for tree-decomposable graphs
• Satisfiability, branch-width and Tseitin tautologies
• Title not available (Why is that?)
• On the role of entanglement in quantum-computational speed-up
• On the complexity of \(k\)-SAT
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Title not available (Why is that?)
• Graph minors. III. Planar tree-width
• Simulating Quantum Computation by Contracting Tensor Networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• Width-parametrized SAT: time-space tradeoffs
• Bounded Round Interactive Proofs in Finite Groups
• Complexity and Algorithms for Well-Structured k-SAT Instances
• Theory and Applications of Satisfiability Testing
• On the satisfiability of quantum circuits of small treewidth

Cited In (6)

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