Generalised phase kick-back: the structure of computational algorithms from physical principles
arXiv:1510.04699 · doi:10.1088/1367-2630/18/3/033023
Abstract
The advent of quantum computing has challenged classical conceptions of which problems are efficiently solvable in our physical world. This motivates the general study of how physical principles bound computational power. In this paper we show that some of the essential machinery of quantum computation -- namely reversible controlled transformations and the phase kick-back mechanism -- exist in any operational-defined theory with a consistent notion of information. These results provide the tools for an exploration of the physics underpinning the structure of computational algorithms. We use these results to investigate the relationship between interference behaviour and computational power, demonstrating that non-trivial interference behaviour is a general resource for post-classical computation. In proving the above, we connect post-quantum interference -- the higher-order interference of Sorkin -- to the existence of post-quantum particle types, potentially providing a novel experimental test for higher-order interference. Finally, we conjecture that theories with post-quantum interference can solve problems intractable even on a quantum computer.
arXiv comment8+4 pages. Updated title, abstract and exposition. Close to journal version
References in corpus (27)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Algorithms Revisited
- Informational derivation of Quantum Theory
- Probabilistic theories with purification
- Quantum Mechanics as Quantum Measure Theory
- The extraction of work from quantum coherence
- Quantum Picturalism
- Higher-order interference and single-system postulates characterizing quantum theory
- Reformulating and Reconstructing Quantum Theory
- All reversible dynamics in maximally non-local theories are trivial
- The structure of reversible computation determines the self-duality of quantum theory
- Quantum Measure Theory and its Interpretation
- Implausible Consequences of Superstrong Nonlocality
- Three Slit Experiments and the Structure of Quantum Theory
- Quantum interference as a resource for quantum speedup
- Density cubes and higher-order interference theories
- Testing Born's Rule in Quantum Mechanics with a Triple Slit Experiment
- Entanglement and thermodynamics in general probabilistic theories
- Higher-order interference in extensions of quantum theory
- Computation in generalised probabilistic theories
- The computational landscape of general physical theories
- Bounding quantum contextuality with lack of third-order intereference
- Entropy, majorization and thermodynamics in general probabilistic theories
- A general framework for phase and interference
- Conditional probability, three-slit experiments, and the Jordan algebra structure of quantum mechanics
- Some Nearly Quantum Theories
- Particle exchange in post-quantum theories
Cited by in corpus (34)
- General probabilistic theories: An introduction
- A no-go theorem on the nature of the gravitational field beyond quantum theory
- Higher-order interference in extensions of quantum theory
- Deriving Grover's lower bound from simple physical principles
- Reconstructing quantum theory from diagrammatic postulates
- The computational landscape of general physical theories
- Ruling out higher-order interference from purity principles
- Accessible fragments of generalized probabilistic theories, cone equivalence, and applications to witnessing nonclassicality
- Quantum computation is the unique reversible circuit model for which bits are balls
- Oracles and query lower bounds in generalised probabilistic theories
- Visualizing Entanglement in multi-Qubit Systems
- Post-quantum steering is a stronger-than-quantum resource for information processing
- Classification of all alternatives to the Born rule in terms of informational properties
- Interferometric computation beyond quantum theory
- Agents, subsystems, and the conservation of information
- On defining the Hamiltonian beyond quantum theory
- On the impossibility of coin-flipping in generalized probabilistic theories via discretizations of semi-infinite programs
- Information-theoretic foundations of thermodynamics in general probabilistic theories
- Compositional resource theories of coherence
- Correlations constrained by composite measurements
- Interference as an information-theoretic game
- Device-independent certification of non-classical joint measurements via causal models
- Exotic looped trajectories via quantum marking
- A no-go theorem for theories that decohere to quantum mechanics
- Simulating all multipartite non-signalling channels via quasiprobabilistic mixtures of local channels in generalised probabilistic theories
- Cosine series quantum sampling method with applications in signal and image processing
- Paradoxical consequences of multipath coherence: perfect interaction-free measurements
- Computation in a general physical setting
- Density Hypercubes, Higher Order Interference and Hyper-Decoherence: a Categorical Approach
- Estimating the Number of States via the Rodeo Algorithm for Quantum Computation
- Process-theoretic characterisation of the Hermitian adjoint
- Complete extension: the non-signaling analog of quantum purification
- Spacetime symmetries and the qubit Bloch ball: a physical derivation of finite dimensional quantum theory and the number of spatial dimensions
- Graph comparison via nonlinear quantum search