Computational Depth Complexity of Measurement-Based Quantum Computation

DOI10.1007/978-3-642-18073-6_4MaRDI QIDQ3070975zbMATH OpenOpenAlexWikidataFDO

Authors Dan E. Browne, Elham Kashefi, Simon Perdrix

Publication date 28 January 2011

Published in Theory of Quantum Computation, Communication, and Cryptography (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: We prove that one-way quantum computations have the same computational power as quantum circuits with unbounded fan-out. It demonstrates that the one-way model is not only one of the most promising models of physical realisation, but also a very powerful model of quantum computation. It confirms and completes previous results which have pointed out, for some specific problems, a depth separation between the one-way model and the quantum circuit model. Since one-way model has the same computational power as unbounded quantum fan-out circuits, the quantum Fourier transform can be approximated in constant depth in the one-way model, and thus the factorisation can be done by a polytime probabilistic classical algorithm which has access to a constant-depth one-way quantum computer. The extra power of the one-way model, comparing with the quantum circuit model, comes from its classical-quantum hybrid nature. We show that this extra power is reduced to the capability to perform unbounded classical parity gates in constant depth.

Recommendations

• Complexity measure: a quantum information approach
• QUANTUM COMPUTATION BY MEASUREMENTS
• Algorithms and Computation
• Quantum Complexity Theory
• Computational complexity of the quantum separability problem
• On quantum complexity
• Quantum implicit computational complexity
• Computing complexity measures for quantum states based on exponential families
• Complexity considerations quantum computation
• State complexity and quantum computation

Cited in

(13)

• Parallelizing quantum circuits
• Determinism and computational power of real measurement-based quantum computation
• Adiabatic graph-state quantum computation
• Collapse of the hierarchy of constant-depth exact quantum circuits
• Computational model underlying the one-way quantum computer
• Ancilla-driven quantum computation with twisted graph states
• Compact Gaussian quantum computation by multi-pixel homodyne detection
• On the need for large Quantum depth
• Computation at a distance
• Entanglement, flow and classical simulatability in measurement based quantum computation
• Anti-heterotic computing
• On the need for large quantum depth
• Theoretical computer science: computational complexity

This page was built for publication: Computational Depth Complexity of Measurement-Based Quantum Computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3070975)