A pseudorandom quantum state (PRS) is an ensemble of quantum states indistinguishable from Haar-random states to observers with efficient quantum computers. It allows one to substitute the costly Haar-random state with efficiently preparable PRS as a resource for cryptographic protocols, while also finding applications in quantum learning theory, black hole physics, many-body thermalization, quantum foundations, and quantum chaos. All existing constructions of PRS equate the notion of efficiency to quantum computers which runtime is bounded by a polynomial in its input size. In this work, we relax the notion of efficiency for PRS with respect to observers with near-term quantum computers implementing algorithms with runtime that scales slower than polynomial-time. We introduce the
T-PRS which is indistinguishable to quantum algorithms with runtime
T(n) that grows slower than polynomials in the input size
n. We give a set of reasonable conditions that a
T-PRS must satisfy and give two constructions by using quantum-secure pseudorandom functions and pseudorandom functions. For
T(n) being linearithmic, linear, polylogarithmic, and logarithmic function, we characterize the amount of quantum resources a
T-PRS must possess, particularly on its coherence, entanglement, and magic. Our quantum resource characterization applies generally to any two state ensembles that are indistinguishable to observers with computational power
T(n), giving a general necessary condition of whether a low-resource ensemble can mimic a high-resource ensemble, forming a
T-pseudoresource pair. We demonstate how the necessary amount of resource decreases as the observer's computational power is more restricted, giving a
T-pseudoresource pair with larger resource gap for more computationally limited observers.
Pseudo-random number generators are widely used in many branches of science, mainly in applications related to Monte Carlo methods, although they are deterministic in design and, therefore, unsuitable for tackling fundamental problems in security and cryptography. The natural laws of the microscopic realm provide a fairly simple method to generate non-deterministic sequences of random numbers, based on measurements of quantum states. In practice, however, the experimental devices on which quantum random number generators are based are often unable to pass some tests of randomness. In this review, we briefly discuss two such tests, point out the challenges that we have encountered and finally present a fairly simple method that successfully generates non-deterministic maximally random sequences.
Physics has two main ambitions: to predict and to understand. Indeed, physics aims for the prediction of all natural phenomena. Prediction entails modeling the correlation between an action, the input, and what is subsequently observed, the output.Understanding, on the other hand, involves developing insightful principles and models that can explain the widest possible varietyof correlations present in nature. Remarkably, advances in both prediction and understanding foster our physical intuition and, as a consequence, novel and powerful applications are discovered. Quantum mechanics is a very successful physical theory both in terms of its predictive power as well as in its wide applicability. Nonetheless and despite many decades of development, we do not yet have a proper physical intuition of quantum phenomena. I believe that improvements in our understanding of quantum theory will yield better, and more innovative, protocols and vice versa.This dissertation aims at advancing our understanding and developing novel protocols. This is done through four approaches. The first one is to study quantum theory within a broad family of theories. In particular, we study quantum theory within the family of locally quantum theories. We found out that the principle that singles out quantum theory out of this family, thus connecting quantum local and nonlocal structure, is dynamical reversibility. This implies that the viability of large scale quantum computing can be based on concrete physical principles that can be experimentally tested at a local level without needing to test millions of qubits simultaneously. The second approach is to study quantum correlations from a black box perspective thus making as few assumptions as possible. The strategy is to study the completeness of quantum predictions by benchmarking them against alternative models. Three main results and applications come out of our study. Firstly, we prove that performing complete amplification of randomness starting from a source of arbitrarily weak randomness - a task that is impossible with classical resources - is indeed possible via nonlocality. This establishes in our opinion the strongest evidence for a truly random event in nature so far. Secondly, we prove that there exist finite events where quantum theory gives predictions as complete as any no-signaling theory can give, showing that the completeness of quantum theory is not an asymptotic property. Finally, we prove that maximally nonlocal theories can never be maximally random while quantum theory can, showing a trade-off between the nonlocality of a theory and its randomness capabilities. We also prove that quantum theory is not unique in this respect. The third approach we follow is to study quantum correlations in scenarios where some parties have a restriction on the available quantum degrees of freedom. The future progress of semi-device-independent quantum information depends crucially on our ability to bound the strength of these correlations. Here we provide a full characterization via a complete hierarchy of sets that approximate the target set from the outside. Each set can be in turn characterized using standard numerical techniques. One application of our work is certifying multidimensional entanglement device-independently.The fourth approach is to confront quantum theory with computer science principles. In particular, we establish two interesting implications for quantum theory results of raising the Church-Turing thesis to the level of postulate. Firstly, we show how different preparations of the same mixed state, indistinguishable according to the quantum postulates, become distinguishable when prepared computably. Secondly, we identify a new loophole for Bell-like experiments: if some parties in a Bell-like experiment use private pseudorandomness to choose their measurement inputs, the computational resources of an eavesdropper have to be limited to observe a proper violation of non locality.
One of the striking properties of quantum mechanics is the occurrence of the Bell-type non-locality. They are a fundamental feature of the theory that allows two parties that share an entangled quantum system to observe correlations stronger than possible in classical physics. In addition to their theoretical significance, non-local correlations have practical applications, such as device-independent randomness generation, providing private unpredictable numbers even when obtained using devices delivered by an untrusted vendor. Thus, determining the quantity of certifiable randomness that can be produced using a specific set of non-local correlations is of significant interest. First, we present an experimental realization of recent Bell-type operators designed to provide private random numbers that are secure against adversaries with quantum resources. We use semi-definite programming to give lower bounds on the generated randomness in terms of both min-entropy and von Neumann entropy in a device-independent scenario. Our results demonstrate the first experiment that certifies nearly two bits of randomness from binary measurements of two parties [1], [2]. Apart from single-round certification, we provide an analysis of finite-key protocol for quantum randomness expansion using the Entropy Accumulation Theorem. Second, we present an efficient and practical method for certifying quantum randomness using generalized measurements. Indeed, we have derived a method for self-testing the presence of POVMs. We present the certification of more than one bit of min-entropy from a single POVM on one of the qubits of an entangled state using a variant of the elegant Bell inequality. We also obtain more than one bit of randomness in a prepare and measure scenario of a similar structure with a POVM on a single qubit [3]. We provide numerical simulations to demonstrate the effectiveness of our randomness certification and expansion.
It has been claimed that to close the locality loophole in a Bell experiment, random numbers of quantum origin should be used for selecting the measurement settings. This is how it has been implemented in all recent Bell experiment addressing this loophole. I point out in this note that quantum random number generators are unnecessary for such experiments and that a Bell experiment with a pseudo-random (but otherwise completely deterministic) mechanism for selecting the measurement settings, such as taking a hash function of the latest million tweets with the hashtag #quantum, would be as convincing, or even more, than one using quantum random number generators.
All maximally entangled two-qubit states violate local realism with the same probability under uniformly random projective measurements, yet they need not behave identically in randomized Bell tests. We show that when measurement settings are exchanged between the parties in sequential Bell experiments, permutation symmetry of the shared state determines the statistical relation between the two realizations. Permutationally invariant states yield identical nonlocality outcomes in both experiments, whereas asymmetric states can violate local realism in one realization but not in the other. This distinction leads to two operational consequences. First, it enables the detection of correlations between the measurement choices of Alice and Bob through the joint violation statistics. Second, in Bell tests with finite measurement pools, asymmetric maximally entangled states can significantly increase the probability of observing nonlocality without requiring additional resources. Our results identify permutation asymmetry as a useful feature in randomized Bell experiments and highlight a new role of symmetry in quantum nonlocality.