Computational Depth Complexity of Measurement-Based Quantum Computation

Dan Browne, Elham Kashefi, Simon Perdrix

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper, we mainly prove that the “depth of computations” in the one-way model is equivalent, up to a classical side-processing of logarithmic depth, to the quantum circuit model augmented with unbounded fanout gates. 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 parallel 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.
Original languageEnglish
Title of host publicationTheory of Quantum Computation, Communication, and Cryptography
Subtitle of host publication5th Conference, TQC 2010, Leeds, UK, April 13-15, 2010, Revised Selected Papers
PublisherSpringer Berlin Heidelberg
Pages35-46
Number of pages12
Volume6519
ISBN (Electronic)978-3-642-18073-6
ISBN (Print)978-3-642-18072-9
DOIs
Publication statusPublished - 2010

Fingerprint

Dive into the research topics of 'Computational Depth Complexity of Measurement-Based Quantum Computation'. Together they form a unique fingerprint.

Cite this