Efficient simulation of random states and random unitaries
From MaRDI portal
Publication:2055680
Abstract: We consider the problem of efficiently simulating random quantum states and random unitary operators, in a manner which is convincing to unbounded adversaries with black-box oracle access. This problem has previously only been considered for restricted adversaries. Against adversaries with an a priori bound on the number of queries, it is well-known that -designs suffice. Against polynomial-time adversaries, one can use pseudorandom states (PRS) and pseudorandom unitaries (PRU), as defined in a recent work of Ji, Liu, and Song; unfortunately, no provably secure construction is known for PRUs. In our setting, we are concerned with unbounded adversaries. Nonetheless, we are able to give stateful quantum algorithms which simulate the ideal object in both settings of interest. In the case of Haar-random states, our simulator is polynomial-time, has negligible error, and can also simulate verification and reflection through the simulated state. This yields an immediate application to quantum money: a money scheme which is information-theoretically unforgeable and untraceable. In the case of Haar-random unitaries, our simulator takes polynomial space, but simulates both forward and inverse access with zero error. These results can be seen as the first significant steps in developing a theory of lazy sampling for random quantum objects.
Recommendations
Cites work
- (Pseudo) random quantum states with binary phase
- Efficient quantum circuits for Schur and Clebsch-Gordan transforms
- Efficient simulation of random states and random unitaries
- How to record quantum queries, and applications to quantum indifferentiability
- scientific article; zbMATH DE number 5901453 (Why is no real title available?)
- scientific article; zbMATH DE number 3960854 (Why is no real title available?)
- Local random quantum circuits are approximate polynomial-designs
- New hash functions and their use in authentication and set equality
- On the power of two-party quantum cryptography
- Positive Functions on C ∗ -Algebras
- Pseudorandom quantum states
- Quantum cryptography: public key distribution and coin tossing
- Quantum proofs of knowledge
- Quantum-secure message authentication codes
- Secure Two-Party Quantum Evaluation of Unitaries against Specious Adversaries
- Security of the Fiat-Shamir transformation in the quantum random-oracle model
- Self testing quantum apparatus
- Small designs for path-connected spaces and path-connected homogeneous spaces
- The Information-Disturbance Tradeoff and the Continuity of Stinespring's Representation
- Unforgeable quantum encryption
- Unitary designs and codes
Cited in
(11)- Efficient simulation of random states and random unitaries
- Scalable pseudorandom quantum states
- (Pseudo) random quantum states with binary phase
- Semi-quantum money
- Tight adaptive reprogramming in the QROM
- Real-valued somewhat-pseudorandom unitaries
- Quantum pseudorandom scramblers
- Simulation of \(n\)-qubit quantum systems. IV. Parametrizations of quantum states, matrices and probability distributions
- On the limitations of pseudorandom unitaries. Or: cryptographic applications of LOCC indistinguishability of identical versus independent Haar unitaries
- Quantum pseudorandom scramblers
- Pseudorandom quantum states
This page was built for publication: Efficient simulation of random states and random unitaries
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2055680)
