Quantum computation is the unique reversible circuit model for which bits are balls

Abstract

The computational efficiency of quantum mechanics can be defined in terms of the qubit circuit model, which is characterized by a few simple properties: each computational gate is a reversible transformation in a connected matrix group; single wires carry quantum bits, i.e. states of a three-dimensional Bloch ball; states on two or more wires are uniquely determined by local measurement statistics and their correlations. In this paper, we ask whether other types of computation are possible if we relax one of those characteristics (and keep all others), namely, if we allow wires to be described by d-dimensional Bloch balls, where d is different from three. Theories of this kind have previously been proposed as possible generalizations of quantum physics, and it has been conjectured that some of them allow for interesting multipartite reversible transformations that cannot be realized within quantum theory. However, here we show that all such potential beyond-quantum models of computation are trivial: if d is not three, then the set of reversible transformations consists entirely of single-bit gates, and not even classical computation is possible. In this sense, qubit quantum computation is an island in theoryspace.

arXiv comment11+4 pages, 2 figures. v2, v3: added some comments, references, and a new title; close to published version

References in corpus (34)

• The Hierarchy Problem and New Dimensions at a Millimeter
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Holographic Derivation of Entanglement Entropy from AdS/CFT
• Thermodynamics of Spacetime: The Einstein Equation of State
• Improved Simulation of Stabilizer Circuits
• Informational derivation of Quantum Theory
• Contextuality supplies the magic for quantum computation
• A derivation of quantum theory from physical requirements
• Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems
• Existence of an information unit as a postulate of quantum theory
• Quantum theory from questions
• All reversible dynamics in maximally non-local theories are trivial
• Deriving quantum theory from its local structure and reversibility
• Generalised phase kick-back: the structure of computational algorithms from physical principles
• Entanglement is an inevitable feature of any non-classical theory
• Entanglement is necessary for emergent classicality in all physical theories
• Toolbox for reconstructing quantum theory from rules on information acquisition
• Deriving Grover's lower bound from simple physical principles
• Computation in generalised probabilistic theories
• Ruling out higher-order interference from purity principles
• Three-dimensionality of space and the quantum bit: an information-theoretic approach
• Hyperbits: the information quasiparticles
• Quantum theory from rules on information acquisition
• Oracles and query lower bounds in generalised probabilistic theories
• An operational approach to spacetime symmetries: Lorentz transformations from quantum communication
• Bounds on the power of proofs and advice in general physical theories
• Some Nearly Quantum Theories
• Classification of all alternatives to the Born rule in terms of informational properties
• Interferometric computation beyond quantum theory
• Derivation of Quantum Theory from Feynman's Rules
• The complex and quaternionic quantum bit from relativity of simultaneity on an interferometer
• Closed Timelike Curves Make Quantum and Classical Computing Equivalent
• Reversible Dynamics in Strongly Non-Local Boxworld Systems
• Is the local linearity of space-time inherited from the linearity of probabilities?

Cited by in corpus (18)

• General probabilistic theories: An introduction
• A no-go theorem on the nature of the gravitational field beyond quantum theory
• Accessible fragments of generalized probabilistic theories, cone equivalence, and applications to witnessing nonclassicality
• Post-quantum steering is a stronger-than-quantum resource for information processing
• Global phase diagram of the one-dimensional Sachdev-Ye-Kitaev model at finite $N$
• Testing quantum theory by generalizing noncontextuality
• The principle of information symmetry constrains the state-space in any physical theory
• Advantage of Quantum Theory Over Non-classical Models of Communication
• Probabilistic Theories and Reconstructions of Quantum Theory (Les Houches 2019 lecture notes)
• On the impossibility of coin-flipping in generalized probabilistic theories via discretizations of semi-infinite programs
• Correlations constrained by composite measurements
• How dynamics constrains probabilities in general probabilistic theories
• Compositional resource theories of coherence
• Computation in a general physical setting
• A Post-Quantum Associative Memory
• Tsirelson's Inequality for the Precession Protocol is Maximally Violated by Quantum Theory
• $su(d)$-squeezing and many-body entanglement geometry in finite-dimensional systems
• Spacetime symmetries and the qubit Bloch ball: a physical derivation of finite dimensional quantum theory and the number of spatial dimensions