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 (34)

• Entanglement detection
• Measuring Quantum Coherence with Entanglement
• Quantum advantage in learning from experiments
• Quantum state discrimination and its applications
• Certified randomness in quantum physics
• Max- relative entropy of coherence: an operational coherence measure
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Wigner function negativity and contextuality in quantum computation on rebits
• Resource theory of imaginarity: Quantification and state conversion
• Scalable measures of magic resource for quantum computers
• Quantum randomness and value indefiniteness
• Quantum commitments and signatures without one-way functions
• Efficient quantum algorithms for stabilizer entropies
• Real quantum operations and state transformations
• Pseudomagic Quantum States
• Quantum Entropy and Central Limit Theorem
• A 2 rebit gate universal for quantum computing
• Learning and Testing Algorithms for the Clifford Group
• Complexity of quantum circuits via sensitivity, magic, and coherence
• Improved Stabilizer Estimation via Bell Difference Sampling
• Pseudorandom density matrices
• Efficient unitary designs and pseudorandom unitaries from permutations
• Efficient Unitary T-designs from Random Sums
• 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
• Fundamental Limitations on Communication over a Quantum Network
• Pseudorandom and Pseudoentangled States from Subset States
• Pseudorandomness from Subset States
• How to Construct Random Unitaries
• 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