Parallelizing Quantum Circuits
arXiv:0704.1736 · doi:10.1016/j.tcs.2008.12.046
Abstract
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.
34 pages, 14 figures; depth complexity, measurement-based quantum computing and parallel computing
References in corpus (10)
- Multi-party entanglement in graph states
- Resource-efficient linear optical quantum computation
- Valence Bond Solids for Quantum Computation
- Quantum Circuit Simplification and Level Compaction
- Generalized Flow and Determinism in Measurement-based Quantum Computation
- An introduction to measurement based quantum computation
- One-way Quantum Computation - a tutorial introduction
- Finding flows in the one-way measurement model
- Phase map decompositions for unitaries
- Complexity of Graph State Preparation
Cited by in corpus (59)
- Unconditionally verifiable blind computation
- Fault-Tolerant High Level Quantum Circuits: Form, Compilation and Description
- There and back again: A circuit extraction tale
- Entanglement spectroscopy with a depth-two quantum circuit
- Optimal preparation of graph states
- Finding Optimal Flows Efficiently
- Qubit-efficient entanglement spectroscopy using qubit resets
- Mapping quantum circuits to modular architectures with QUBO
- No-go Theorem for One-way Quantum Computing on Naturally Occurring Two-level Systems
- Measurement-Based Quantum Computation
- Finding flows in the one-way measurement model
- Information Flow in Secret Sharing Protocols
- Circuit Design for A Measurement-Based Quantum Carry-Lookahead Adder
- Quantum circuit optimization by topological compaction in the surface code
- Closed timelike curves in measurement-based quantum computation
- Towards Minimal Resources of Measurement-based Quantum Computation
- A Statistical Theory of Designed Quantum Transport Across Disordered Networks
- A direct approach to Gaussian measurement based quantum computation
- An analysis of the trade-off between spatial and temporal resources for measurement-based quantum computation
- Optimizing Quantum Programs against Decoherence: Delaying Qubits into Quantum Superposition
- Non-Identity Check Remains QMA-Complete for Short Circuits
- Complete Flow-Preserving Rewrite Rules for MBQC Patterns with Pauli Measurements
- Parallel Quantum Algorithm for Hamiltonian Simulation
- Flow-preserving ZX-calculus Rewrite Rules for Optimisation and Obfuscation
- Ancilla-driven quantum computation for qudits and continuous variables
- Minimal physical resources for the realisation of measurement-based quantum computation
- Quantum Volume for Photonic Quantum Processors
- Computational Distinguishability of Quantum Channels
- Compact quantum circuits from one-way quantum computation
- Scanning qubit probe of edge states in a topological insulator
- Distinguishing Short Quantum Computations
- Ancilla-free Quantum Adder with Sublinear Depth
- Quantum computation mediated by ancillary qudits and spin coherent states
- Outcome determinism in measurement-based quantum computation with qudits
- Geometry-Based Optimization of One-Way Quantum Computation Measurement Patterns
- Resource optimization for fault-tolerant quantum computing
- Flow conditions for continuous variable measurement-based quantum computing
- Methods for Classically Simulating Noisy Networked Quantum Architectures
- Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs
- Reversibility in the Extended Measurement-based Quantum Computation
- Quantum-Logic Synthesis of Hermitian Gates
- Measurement-based quantum machine learning
- Test of Quantumness with Small-Depth Quantum Circuits
- Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
- Implementing a Fast Unbounded Quantum Fanout Gate Using Power-Law Interactions
- Path Matters: Industrial Data Meet Quantum Optimization
- Parallel remote state preparation for fully device-independent verifiable blind quantum computation
- Quantum Theory from Principles, Quantum Software from Diagrams
- One-Way Quantum Computer Simulation
- Decomposition of Diagonal Hermitian Quantum Gates Using Multiple-Controlled Pauli Z Gates
- An extremal result for geometries in the one-way measurement model
- Entanglement, Flow and Classical Simulatability in Measurement Based Quantum Computation
- Reducing depth and measurement weights in Pauli-based computation
- Quantum circuit optimization for unitary operators over non-adjacent qudits
- Inserting Planar-Measured Qubits into MBQC Patterns while Preserving Flow
- Quantum Oracles in Constant Depth with Measurement-Based Quantum Computation
- Benincasa-Dowker-Glaser causal set actions by quantum counting
- Quadratic Form Expansions for Unitaries
- Simplifying errors by symmetry and randomisation