Quantum Computing and Hidden Variables I: Mapping Unitary to Stochastic Matrices
arXiv:quant-ph/0408035 · doi:10.1103/PhysRevA.71.032325
Abstract
This paper initiates the study of hidden variables from the discrete, abstract perspective of quantum computing. For us, a hidden-variable theory is simply a way to convert a unitary matrix that maps one quantum state to another, into a stochastic matrix that maps the initial probability distribution to the final one in some fixed basis. We list seven axioms that we might want such a theory to satisfy, and then investigate which of the axioms can be satisfied simultaneously. Toward this end, we construct a new hidden-variable theory that is both robust to small perturbations and indifferent to the identity operation, by exploiting an unexpected connection between unitary matrices and network flows. We also analyze previous hidden-variable theories of Dieks and Schrodinger in terms of our axioms. In a companion paper, we will show that actually sampling the history of a hidden variable under reasonable axioms is at least as hard as solving the Graph Isomorphism problem; and indeed is probably intractable even for quantum computers.
19 pages, 1 figure. Together with a companion paper to appear, subsumes the earlier paper "Quantum Computing and Dynamical Quantum Models" (quant-ph/0205059)
References in corpus (3)
Cited by in corpus (28)
- NP-complete Problems and Physical Reality
- Implications of the Pusey-Barrett-Rudolph quantum no-go theorem
- Exponential complexity and ontological theories of quantum mechanics
- Efficient Hidden-Variable Simulation of Measurements in Quantum Experiments
- Ontological models and the interpretation of contextuality
- A review of matrix scaling and Sinkhorn's normal form for matrices and positive maps
- Dynamics of a qubit as a classical stochastic process with time-correlated noise: minimal measurement invasiveness
- Q-functions as models of physical reality
- Limits on Efficient Computation in the Physical World
- On bipartite unitary matrices generating subalgebra-preserving quantum operations
- Simulation of Quantum Walks and Fast Mixing with Classical Processes
- Conditions for the compatibility of channels in general probabilistic theory and their connection to steering and Bell nonlocality
- Scaling a unitary matrix
- Space-bounded Church-Turing thesis and computational tractability of closed systems
- On the sampling complexity of open quantum systems
- Divisible quantum dynamics satisfies temporal Tsirelson's bound
- Economical ontological models for discrete quantum systems
- Quantum Computing and Hidden Variables II: The Complexity of Sampling Histories
- Subspace projection method for unstructured searches with noisy quantum oracles using a signal-based quantum emulation device
- Bell's Jump Process in Discrete Time
- Probability in many-worlds theories
- A Simplified Basis for Bell-Kochen-Specker Theorems
- Bounding the convergence time of local probabilistic evolution
- Violating the assumption of Measurement Independence in Quantum Foundations
- Local Probability Conservation in Discrete Time Quantum Walks
- Superposition detection and QMA with non-collapsing measurements
- A hierarchy in Majorana non-abelian tests and hidden variable models
- Simulation of Quantum Correlation Functions is not Sufficient Resource to Describe Quantum Entanglement