Physics – Quantum Physics
Scientific paper
2007-04-13
Theoretical Computer Science, Volume 410, Issue 26, 2009
Physics
Quantum Physics
34 pages, 14 figures; depth complexity, measurement-based quantum computing and parallel computing
Scientific paper
10.1016/j.tcs.2008.12.046
We present a novel automated technique for parallelizing quantum circuits via forward and backward translation to measurement-based quantum computing patterns and analyze the trade off in terms of depth and space complexity. As a result we distinguish a class of polynomial depth circuits that can be parallelized to logarithmic depth while adding only polynomial many auxiliary qubits. In particular, we provide for the first time a full characterization of patterns with flow of arbitrary depth, based on the notion of influencing paths and a simple rewriting system on the angles of the measurement. Our method leads to insightful knowledge for constructing parallel circuits and as applications, we demonstrate several constant and logarithmic depth circuits. Furthermore, we prove a logarithmic separation in terms of quantum depth between the quantum circuit model and the measurement-based model.
Broadbent Anne
Kashefi Elham
No associations
LandOfFree
Parallelizing Quantum Circuits 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 Parallelizing Quantum Circuits, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallelizing Quantum Circuits will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-678346