Pseudorandom States, Non-Cloning Theorems and Quantum Money

Abstract

We propose the concept of pseudorandom states and study their constructions, properties, and applications. Under the assumption that quantum-secure one-way functions exist, we present concrete and efficient constructions of pseudorandom states. The non-cloning theorem plays a central role in our study---it motivates the proper definition and characterizes one of the important properties of pseudorandom quantum states. Namely, there is no efficient quantum algorithm that can create more copies of the state from a given number of pseudorandom states. As the main application, we prove that any family of pseudorandom states naturally gives rise to a private-key quantum money scheme.

20 pages

References in corpus (7)

• Aspects of generic entanglement
• Twelve years before the quantum no-cloning theorem
• Quantum Money from Hidden Subspaces
• Efficient Quantum Tensor Product Expanders and k-designs
• Efficient quantum pseudorandomness with simple graph states
• An online attack against Wiesner's quantum money
• Computational Notions of Quantum Min-Entropy

Cited by in corpus (52)

• Quantum advantage in learning from experiments
• Models of quantum complexity growth
• Quantum Algorithmic Measurement
• Quantum commitments and signatures without one-way functions
• The ghost in the radiation: Robust encodings of the black hole interior
• Quantum Cryptography in Algorithmica
• Finding Pythons in Unexpected Places
• A Quantum Money Solution to the Blockchain Scalability Problem
• Quantum Pseudorandomness and Classical Complexity
• Semi-Quantum Money
• Improved Stabilizer Estimation via Bell Difference Sampling
• Pseudorandom unitaries are neither real nor sparse nor noise-robust
• Efficient simulation of random states and random unitaries
• Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality
• Quantum Topological Data Analysis with Linear Depth and Exponential Speedup
• Efficient Unitary T-designs from Random Sums
• Efficient unitary designs and pseudorandom unitaries from permutations
• Estimating the randomness of quantum circuit ensembles up to 50 qubits
• Dynamics of Pseudoentanglement
• Weak approximate unitary designs and applications to quantum encryption
• Efficient distributed inner product estimation via Pauli sampling
• Holographic deep thermalization for secure and efficient quantum random state generation
• Unconditionally Secure Commitments with Quantum Auxiliary Inputs
• Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates
• Oblivious Transfer from Zero-Knowledge Proofs, or How to Achieve Round-Optimal Quantum Oblivious Transfer and Zero-Knowledge Proofs on Quantum States
• Efficient witnessing and testing of magic in mixed quantum states
• A Unified Framework For Quantum Unforgeability
• Trade-off between Gradient Measurement Efficiency and Expressivity in Deep Quantum Neural Networks
• Quantum Unpredictability
• Quantum-Computable One-Way Functions without One-Way Functions
• Emergent unitary designs for encoded qubits from coherent errors and syndrome measurements
• Non-Clifford Cost of Random Unitaries
• On the Computational Hardness of Quantum One-Wayness
• Quantum Merkle Trees
• Fast pseudorandom quantum state generators via inflationary quantum gates
• Quasi-Chaotic Oscillators Based on Modular Quantum Circuits
• A New World in the Depths of Microcrypt: Separating OWSGs and Quantum Money from QEFID
• Overlapping qubits from non-isometric maps and de Sitter tensor networks
• On Computational Complexity of Unitary and State Design Properties
• Gluing Random Unitaries with Inverses and Applications to Strong Pseudorandom Unitaries
• Pseudorandom Unitaries in the Haar Random Oracle Model
• Pseudochaotic Many-Body Dynamics as a Pseudorandom State Generator
• New Approaches for Quantum Copy-Protection
• How to Sign Quantum Messages
• Estimating time in quantum chaotic systems and black holes
• Quantum Chebyshev's Inequality and Applications
• A Note on Output Length of One-Way State Generators and EFIs
• Cryptographic Characterization of Quantum Advantage
• Quantum Cryptography and Meta-Complexity
• Topologically driven no-superposing theorem with a tight error bound
• Quantum Merlin-Arthur proof systems for synthesizing quantum states
• Almost Public Quantum Coins