Journal
THEORETICAL COMPUTER SCIENCE
Volume 410, Issue 26, Pages 2489-2510Publisher
ELSEVIER
DOI: 10.1016/j.tcs.2008.12.046
Keywords
Quantum circuits; Circuit depth; Measurement-based quantum computing; Measurement calculus
Categories
Funding
- NSERC
- FQRNT
- CFUW
- ARO-DTO
- Universite de Montreal
- EPSRC [EP/E059600/1] Funding Source: UKRI
- Engineering and Physical Sciences Research Council [EP/E059600/1] Funding Source: researchfish
Ask authors/readers for more resources
We present a novel automated technique for parallelizing quantum circuits via the 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 a polynomial number of 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 walks and a simple rewriting system on the angles of the measurement. Our method provides new insight for constructing parallel circuits and as applications, we demonstrate several classes of circuits that can be parallelized to constant or logarithmic depth. Furthermore, we prove a logarithmic separation in terms of quantum depth between the quantum circuit model and the measurement-based model. (C) 2009 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available