Pseudorandom unitaries are neither real nor sparse nor noise-robust

Abstract

Pseudorandom quantum states (PRSs) and pseudorandom unitaries (PRUs) possess the dual nature of being efficiently constructible while appearing completely random to any efficient quantum algorithm. In this study, we establish fundamental bounds on pseudorandomness. We show that PRSs and PRUs exist only when the probability that an error occurs is negligible, ruling out their generation on noisy intermediate-scale and early fault-tolerant quantum computers. Further, we show that PRUs need imaginarity while PRS do not have this restriction. This implies that quantum randomness requires in general a complex-valued formalism of quantum mechanics, while for random quantum states real numbers suffice. Additionally, we derive lower bounds on the coherence of PRSs and PRUs, ruling out the existence of sparse PRUs and PRSs. We also show that the notions of PRS, PRUs and pseudorandom scramblers (PRSSs) are distinct in terms of resource requirements. We introduce the concept of pseudoresources, where states which contain a low amount of a given resource masquerade as high-resource states. We define pseudocoherence, pseudopurity and pseudoimaginarity, and identify three distinct types of pseudoresources in terms of their masquerading capabilities. Our work also establishes rigorous bounds on the efficiency of property testing, demonstrating the exponential complexity in distinguishing real quantum states from imaginary ones, in contrast to the efficient measurability of unitary imaginarity. Further, we show an exponential advantage in imaginarity testing when having access to the complex conjugate of the state. Lastly, we show that the transformation from a complex to a real model of quantum computation is inefficient, in contrast to the reverse process, which is efficient. Our results establish fundamental limits on property testing and provide valuable insights into quantum pseudorandomness.

14+12 pages, 2 figures

References in corpus (82)

• Quantifying Coherence
• Entanglement detection
• Noisy intermediate-scale quantum (NISQ) algorithms
• Quantum Coherence as a Resource
• Quantum Resource Theories
• Measurement-based quantum computation
• The foundations of statistical mechanics from entanglement: Individual states vs. averages
• Measuring Quantum Coherence with Entanglement
• Integration with respect to the Haar measure on unitary, orthogonal and symplectic group
• Quantum advantage in learning from experiments
• The Resource Theory of Stabilizer Computation
• Instantaneous non-local computation of low T-depth quantum circuits
• Quantum random number generation
• Direct estimations of linear and non-linear functionals of a quantum state
• Universal Quantum Estimator
• Quantum-assisted quantum compiling
• Quantum state discrimination and its applications
• Local random quantum circuits are approximate polynomial-designs
• Certified randomness in quantum physics
• When Entanglement meets Classical Communications: Quantum Teleportation for the Quantum Internet (Invited Paper)
• Stabilizer Rényi entropy
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Coherence as a resource in decision problems: The Deutsch-Jozsa algorithm and a variation
• Relating the Resource Theories of Entanglement and Quantum Coherence
• Random Quantum Circuits and Pseudo-Random Operators: Theory and Applications
• Quantum theory based on real numbers can be experimentally falsified
• Max- relative entropy of coherence: an operational coherence measure
• Coherence depletion in the Grover quantum search algorithm
• Operational Resource Theory of Imaginarity
• Quantum randomness extraction for various levels of characterization of the devices
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Wigner function negativity and contextuality in quantum computation on rebits
• Quantum error mitigation as a universal error-minimization technique: applications from NISQ to FTQC eras
• Quantifying the Imaginarity of Quantum Mechanics
• Pseudorandom States, Non-Cloning Theorems and Quantum Money
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Ruling out real-valued standard formalism of quantum theory
• Resource theory of imaginarity: Quantification and state conversion
• Scalable measures of magic resource for quantum computers
• Schur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations
• Randomness in Quantum Mechanics: Philosophy, Physics and Technology
• Quantum randomness and value indefiniteness
• Efficient unitary designs with nearly time-independent Hamiltonian dynamics
• Minimizing estimation runtime on noisy quantum computers
• Cohering power of quantum operations
• Quantum commitments and signatures without one-way functions
• Symbolic integration with respect to the Haar measure on the unitary group
• Coherence generating power of quantum unitary maps and beyond
• Efficient quantum algorithms for stabilizer entropies
• Average coherence and its typicality for random pure states
• On the statistical complexity of quantum circuits
• Efficient Quantum Pseudorandomness
• Efficient classical simulation of Clifford circuits with nonstabilizer input states
• Pseudomagic Quantum States
• Real quantum operations and state transformations
• Quantum Entropy and Central Limit Theorem
• A 2 rebit gate universal for quantum computing
• Learning and Testing Algorithms for the Clifford Group
• Property testing of unitary operators
• Quantum Pseudorandomness and Classical Complexity
• Complex conjugation supermap of unitary quantum maps and its universal implementation protocol
• Certifying quantumness: Benchmarks for the optimal processing of generalized coherent and squeezed states
• Complexity of quantum circuits via sensitivity, magic, and coherence
• Improved Stabilizer Estimation via Bell Difference Sampling
• Pseudorandom density matrices
• Efficient Unitary T-designs from Random Sums
• Efficient unitary designs and pseudorandom unitaries from permutations
• Complexity Classification of Conjugated Clifford Circuits
• Quantum simulation from the bottom up: the case of rebits
• Entanglement Scaling in Quantum Advantage Benchmarks
• On the power quantum computation over real Hilbert spaces
• Efficient Learning of Continuous-Variable Quantum States
• Exponential learning advantages with conjugate states and minimal quantum memory
• Random unitaries in extremely low depth
• Discrete Quantum Gaussians and Central Limit Theorem
• Simple constructions of linear-depth t-designs and pseudorandom unitaries
• Pseudorandom and Pseudoentangled States from Subset States
• How to Construct Random Unitaries
• Pseudorandomness from Subset States
• Fundamental Limitations on Communication over a Quantum Network
• Pseudorandom unitaries with non-adaptive security
• Real-Valued Somewhat-Pseudorandom Unitaries

Cited by in corpus (15)

• Probing quantum complexity via universal saturation of stabilizer entropies
• Efficient distributed inner product estimation via Pauli sampling
• Efficient witnessing and testing of magic in mixed quantum states
• Anticoncentration and State Design of Doped Real Clifford Circuits and Tensor Networks
• Coherence and Imaginarity as Resources in Quantum Circuit Complexity
• Non-Clifford Cost of Random Unitaries
• Analyzing the free states of one quantum resource theory as resource states of another
• Imaginarity measures induced by real part states and the complementarity relations
• Anticoncentration in Clifford Circuits and Beyond: From Random Tensor Networks to Pseudo-Magic States
• On the Hardness of Measuring Magic
• Bell sampling in Quantum Monte Carlo simulations
• Shallow quantum circuit for generating extremely low-entangled approximate state designs
• Experimental certification of the nonlocal advantages of quantum imaginarity
• Measure of set imaginarity
• Adaptively secure unitary designs with constant non-Clifford cost