Algorithmic Pseudorandomness in Quantum Setups

Abstract

The Church-Turing thesis is one of the pillars of computer science; it postulates that every classical system has equivalent computability power to the so-called Turing machine. While this thesis is crucial for our understanding of computing devices, its implications in other scientific fields have hardly been explored. Here we start this research programme in the context of quantum physics and show that computer science laws have profound implications for some of the most fundamental results of the theory. We first show how they question our knowledge on what a mixed quantum state is, as we identify situations in which ensembles of quantum states defining the same mixed state, indistinguishable according to the quantum postulates, do become distinguishable when prepared by a computer. We also show a new loophole for Bell-like experiments: if some of the parties in a Bell-like experiment use a computer to decide which measurements to make, then the computational resources of an eavesdropper have to be limited in order to have a proper observation of non-locality. Our work opens a new direction in the search for a framework unifying computer science and quantum physics.

4 pages+8 pages appendix, 4 figures

References in corpus (9)

• Experimental loophole-free violation of a Bell inequality using entangled electron spins separated by 1.3 km
• Significant-loophole-free test of Bell's theorem with entangled photons
• A strong loophole-free test of local realism
• The Free Will Theorem
• Local deterministic model of singlet state correlations based on relaxing measurement independence
• No extension of quantum theory can have improved predictive power
• Generation of fresh and pure random numbers for loophole-free Bell tests
• Experimental bound entanglement in a four-photon state
• The effects of reduced "free will" on Bell-based randomness expansion

Cited by in corpus (5)

• Randomness? What randomness?
• Algorithmic independence of initial condition and dynamical law in thermodynamics and causal inference
• Detection Efficiency Bounds in (Semi-)Device-Independent Scenarios
• Impossibility of memory in hidden-signaling models for quantum correlations
• Distinguishing computable mixtures of quantum states