How to Construct Random Unitaries
The existence of pseudorandom unitaries (PRUs) -- efficient quantum circuits that are computationally indistinguishable from Haar-random unitaries -- has been a central open question, with significant implications for cryptography, complexity theory, and fundamental physics. In this work, we close this question by proving that PRUs exist, assuming that any quantum-secure one-way function exists. We establish this result for both (1) the standard notion of PRUs, which are secure against any efficient adversary that makes queries to the unitary $U$, and (2) a stronger notion of PRUs, which are secure even against adversaries that can query both the unitary $U$ and its inverse $U^\dagger$. In the process, we prove that any algorithm that makes queries to a Haar-random unitary can be efficiently simulated on a quantum computer, up to inverse-exponential trace distance.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Gradient descent reliably finds depth- and gate-optimal circuits for generic unitaries
When the gate set has continuous parameters, synthesizing a unitary operator as a quantum circuit is, in principle, always possible using exact methods. However, efficiently finding depth- and gate-minimal circuits remai…
Mildly-Interacting Fermionic Unitaries are Efficiently Learnable
Recent work has shown that one can efficiently learn fermionic Gaussian unitaries, also commonly known as nearest-neighbor matchcircuits or non-interacting fermionic unitaries. However, one could ask a similar question a…
AI methods for approximate compiling of unitaries
This paper explores artificial intelligence (AI) methods for the approximate compiling of unitaries, focusing on the use of fixed two-qubit gates and arbitrary single-qubit rotations typical in superconducting hardware. …
Noise-tolerant learnability of shallow quantum circuits from statistics and the cost of quantum pseudorandomness
In this work, we study the learnability of quantum circuits in the near term. We demonstrate the natural robustness of quantum statistical queries for learning quantum processes, motivating their use as a theoretical too…
Learning Quantum Processes with Quantum Statistical Queries
In this work, we initiate the study of learning quantum processes from quantum statistical queries. We focus on two fundamental learning tasks in this new access model: shadow tomography of quantum processes and process …
BenchmarkingCryptanalysisQuantum Machine Learning