Matchgate and space-bounded quantum computations are equivalent

DOI10.1098/rspa.2009.0433zbMath1195.81034arXiv0908.1467OpenAlexW3098366347WikidataQ63198946 ScholiaQ63198946MaRDI QIDQ4931028

Akimasa Miyake, John Watrous, Barbara Kraus, Richard Jozsa

Publication date: 2 October 2010

Published in: Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences (Search for Journal in Brave)

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

zbMATH Keywords

space-bounded computationquantum computational complexityquantum matchgates

Mathematics Subject Classification ID

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

Related Items (7)

Commuting quantum circuits and complexity of Ising partition functions ⋮ A Complete Characterization of Unitary Quantum Space ⋮ Effective simulation of state distribution in qubit chains ⋮ Clifford gates in the Holant framework ⋮ Quantum matchgate computations and linear threshold gates ⋮ Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy ⋮ Clifford Algebras, Spin Groups and Qubit Trees

Cites Work

• Matchgates and classical simulation of quantum circuits

This page was built for publication: Matchgate and space-bounded quantum computations are equivalent