Quantum Circuits with Mixed States
arXiv:quant-ph/9806029
Abstract
We define the model of quantum circuits with density matrices, where non-unitary gates are allowed. Measurements in the middle of the computation, noise and decoherence are implemented in a natural way in this model, which is shown to be equivalent in computational power to standard quantum circuits. The main result in this paper is a solution for the subroutine problem: The general function that a quantum circuit outputs is a probabilistic function, but using pure state language, such a function can not be used as a black box in other computations. We give a natural definition of using general subroutines, and analyze their computational power. We suggest convenient metrics for quantum computing with mixed states. For density matrices we analyze the so called ``trace metric'', and using this metric, we define and discuss the ``diamond metric'' on superoperators. These metrics enable a formal discussion of errors in the computation. Using a ``causality'' lemma for density matrices, we also prove a simple lower bound for probabilistic functions.
20 pages, Latex. In ``Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computation (STOC)'', pages 20-30, 1997
Cited by in corpus (43)
- Simulating quantum computation by contracting tensor networks
- Quantum speedup of Monte Carlo methods
- Quantum Network Coding
- Quantum Computational Complexity -- From Quantum Information to Black Holes and Back
- Subsystem Complexity and Holography
- Optimal lower bounds for quantum automata and random access codes
- Quantum Computer with Mixed States and Four-Valued Logic
- Entanglement Entropy and Complexity for One-Dimensional Holographic Superconductors
- Operational distance and fidelity for quantum channels
- How energy conservation limits our measurements
- Simple master equations for describing driven systems subject to classical non-Markovian noise
- Accrediting outputs of noisy intermediate-scale quantum computing devices
- Succinct quantum proofs for properties of finite groups
- A direct sum theorem in communication complexity via message compression
- On quantum and approximate privacy
- Measurement-based quantum computation in finite one-dimensional systems: string order implies computational power
- Quantum Strategies and Local Operations
- The Efficiency of Quantum Identity Testing of Multiple States
- Ancilla dimension in quantum channel discrimination
- Computing Stabilized Norms for Quantum Operations via the Theory of Completely Bounded Maps
- Quantum Gate Generation in Two-Level Open Quantum Systems by Coherent and Incoherent Photons Found with Gradient Search
- Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete
- A lower bound for bounded round quantum communication complexity of set disjointness
- Quantum Walks On Graphs
- Classical and quantum computation with small space bounds (PhD thesis)
- Directed quantum communication
- Zero-knowledge against quantum attacks
- Dynamical Aspects of Information Storage in Quantum-Mechanical Systems
- Lower bounds for predecessor searching in the cell probe model
- Two-way finite automata with quantum and classical states
- Quantum Approximation of Normalized Schatten Norms and Applications to Learning
- Structuring quantum effects: superoperators as arrows
- Quantum Multi-Prover Interactive Proof Systems with Limited Prior Entanglement
- A New Protocol and Lower Bounds for Quantum Coin Flipping
- On quantum and classical space-bounded processes with algebraic transition amplitudes
- Equilibration and Typicality in Quantum Processes
- On the hardness of distinguishing mixed-state quantum computations
- Succinctness of two-way probabilistic and quantum finite automata
- Using Entanglement in Quantum Multi-Prover Interactive Proofs
- Lower bounds in the quantum cell probe model
- Quantum Formulas: a Lower Bound and Simulation
- Characterizations of one-way general quantum finite automata
- General Properties of Quantum Zero-Knowledge Proofs