Counting single-qubit Clifford equivalent graph states is #P-complete
DOI10.1063/1.5120591zbMath1443.81021arXiv1907.08024OpenAlexW3104857786MaRDI QIDQ5110740
Stephanie Wehner, Jonas Helsen, Axel Dahlberg
Publication date: 22 May 2020
Published in: Journal of Mathematical Physics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1907.08024
Applications of graph theory (05C90) Quantum computation (81P68) Quantum coherence, entanglement, quantum correlations (81P40) Quantum information, communication, networks (quantum-theoretic aspects) (81P45) Quantum mechanics on special spaces: manifolds, fractals, graphs, lattices (81Q35) Computational stability and error-correcting codes for quantum computation and communication processing (81P73)
Uses Software
Cites Work
- Unnamed Item
- The complexity of computing the permanent
- Recognizing locally equivalent graphs
- On the classification of all self-dual additive codes over \(\text{GF}(4)\) of length up to 12
- Vertex-minors, monadic second-order logic, and a conjecture by Seese
- Isotropic systems
- Graphic presentations of isotropic systems
- An efficient algorithm to recognize locally equivalent graphs
- Circle graph obstructions
- Algorithmic graph theory and perfect graphs
- The complexity of counting Eulerian tours in 4-regular graphs
- Rank-width and vertex-minors
- Transforming graph states using single-qubit operations
- Graph states for quantum secret sharing
- Quantitative Monadic Second-Order Logic
- Quantum Anonymous Transmissions
- An algorithm for finding a fundamental set of cycles of a graph
- The complexity of theorem-proving procedures
This page was built for publication: Counting single-qubit Clifford equivalent graph states is #P-complete
