Physics – Quantum Physics
Scientific paper
2009-09-25
In Proceeding of the Fifth Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2010), Leeds 2
Physics
Quantum Physics
12 pages
Scientific paper
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.
Browne Dan E.
Kashefi Elham
Perdrix Simon
No associations
LandOfFree
Computational depth complexity of measurement-based quantum computation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Computational depth complexity of measurement-based quantum computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computational depth complexity of measurement-based quantum computation will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-325818