Quantum pseudorandomness, also known as unitary designs, comprises a powerful resource for emergent quantum technologies. Although in theory pseudorandom unitary operators can be constructed efficiently, realizing these objects in realistic physical systems is a challenging task. Here, we demonstrate experimental generation and detection of quantum pseudorandomness on a 12-qubit nuclear magnetic resonance system. We first apply random sequences to the interacting nuclear spins, leading to random quantum evolutions that can quickly form unitary designs. Then, in order to probe the growth of quantum pseudorandomness during the time evolutions, we propose the idea of using the system's multiple-quantum coherence distribution as an indicator. Based on this indicator, we measure the spreading of quantum coherences and find that substantial quantum pseudorandomness has been achieved at the 12-qubit scale. This may open up a path to experimentally explore quantum randomness on forthcoming large-scale quantum processors.
Quantum pseudorandomness, also known as unitary designs, comprises a powerful resource for emergent quantum technologies. Although in theory pseudorandom unitary operators can be constructed efficiently, realizing these objects in realistic physical systems is a challenging task. Here, we demonstrate experimental generation and detection of quantum pseudorandomness on a 12-qubit nuclear magnetic resonance system. We first apply random sequences to the interacting nuclear spins, leading to random quantum evolutions that can quickly form unitary designs. Then, in order to probe the growth of quantum pseudorandomness during the time evolutions, we propose the idea of using the system's multiple-quantum coherence distribution as an indicator. Based on this indicator, we measure the spreading of quantum coherences and find that substantial quantum pseudorandomness has been achieved at the 12-qubit scale. This may open up a path to experimentally explore quantum randomness on forthcoming large-scale quantum processors.
Randomness is both a useful way to model natural systems and a useful tool for engineered systems, e.g., in computation, communication, and control. Fully random transformations require exponential time for either classical or quantum systems, but in many cases pseudorandom operations can emulate certain properties of truly random ones. Indeed, in the classical realm there is by now a well-developed theory regarding such pseudorandom operations. However, the construction of such objects turns out to be much harder in the quantum case. Here, we show that random quantum unitary time evolutions ("circuits") are a powerful source of quantum pseudorandomness. This gives for the first time a polynomial-time construction of quantum unitary designs, which can replace fully random operations in most applications, and shows that generic quantum dynamics cannot be distinguished from truly random processes. We discuss applications of our result to quantum information science, cryptography, and understanding the self-equilibration of closed quantum dynamics.
Can simple processes appear highly complex? Gowers (Comb. Prob. Comp. '96) conjectured that repeatedly composing local random reversible operations can yield global permutations that are indistinguishable from random. In this work, we study the unitary quantum analog of this question, in an attempt to make new progress on this longstanding conjecture.
Our first result shows that statistical moment matching in the form of unitary designs does not generically lead to pseudorandomness---even for the simplest quantum processes: for every fixed t, we give an efficiently samplable family {νn}n of distributions on one- and two-qubit gates such that, after T=Ot(n2log2n) independent steps, the resulting n-qubit ensemble is an approximate unitary t-design with negligible error exp(−Ω(log2n)), yet an efficient quantum algorithm distinguishes it from random using only Ot(log2n) queries. This refutes the unitary analog of the Hoory--Magen--Myers--Rackoff conjecture (ICALP '04) for permutations.
Our second result is a stronger separation between unitary designs and pseudorandom unitaries at polynomially bounded moments; our counterexample, however, requires highly structured ensembles, in contrast with the simple local walks from before. This suggests caution when using unitary designs to model information scrambling in black-hole physics, as even maximally scrambled systems can exhibit structure which is accessible to efficient experiments. Motivated by these findings, we then propose new conjectures for how pseudorandomness can plausibly emerge within simple quantum processes, such as random quantum circuits.
In close analogy to the fundamental role of random numbers in classical information theory, random operators are a basic component of quantum information theory. Unfortunately, the implementation of random unitary operators on a quantum processor is exponentially hard. Here we introduce a method for generating pseudo-random unitary operators that can reproduce those statistical properties of random unitary operators most relevant to quantum information tasks. This method requires exponentially fewer resources, and hence enables the practical application of random unitary operators in quantum communication and information processing protocols. Using a nuclear magnetic resonance quantum processor, we were able to realize pseudorandom unitary operators that reproduce the expected random distribution of matrix elements.
The nature of randomness and complexity growth in systems governed by unitary dynamics is a fundamental question in quantum many-body physics. This problem has motivated the study of models such as local random circuits and their convergence to Haar-random unitaries in the long-time limit. However, these models do not correspond to any family of physical time-independent Hamiltonians. In this work, we address this gap by studying the indistinguishability of time-independent Hamiltonian dynamics from truly random unitaries. On one hand, we establish a no-go result showing that for any ensemble of constant-local Hamiltonians and any evolution times, the resulting time-evolution unitary can be efficiently distinguished from Haar-random and fails to form a 2-design or a pseudorandom unitary (PRU). On the other hand, we prove that this limitation can be overcome by increasing the locality slightly: there exist ensembles of random polylog-local Hamiltonians in one-dimension such that under constant evolution time, the resulting time-evolution unitary is indistinguishable from Haar-random, i.e. it forms both a unitary k-design and a PRU. Moreover, these Hamiltonians can be efficiently simulated under standard cryptographic assumptions.
The efficiency of locally generating unitary designs, which capture statistical notions of quantum pseudorandomness, lies at the heart of wide-ranging areas in physics and quantum information technologies. While there are extensive potent methods and results for this problem, the evidently important setting where continuous symmetries or conservation laws (most notably U(1) and SU(d)) are involved is known to present fundamental difficulties. In particular, even the basic question of whether any local symmetric circuit can generate 2-designs efficiently (in time that grows at most polynomially in the system size) remains open with no circuit constructions provably known to do so, despite intensive efforts. In this work, we resolve this long-standing open problem for both U(1) and SU(d) symmetries by explicitly constructing local symmetric quantum circuits which we prove to converge to symmetric unitary 2-designs in polynomial time using a combination of representation theory, graph theory, and Markov chain methods. As a direct application, our constructions can be used to efficiently generate near-optimal covariant quantum error-correcting codes, confirming a conjecture in [PRX Quantum 3, 020314 (2022)].
Random unitaries are a central object of study in quantum information, with applications to quantum computation, quantum many-body physics, and quantum cryptography. Recent work has constructed unitary designs and pseudorandom unitaries (PRUs) using Θ(loglogn)-depth unitary circuits with two-qubit gates. In this work, we show that unitary designs and PRUs can be efficiently constructed in several well-studied models of constant-time quantum computation (i.e., the time complexity on the quantum computer is independent of the system size). These models are constant-depth circuits augmented with certain nonlocal operations, such as (a) many-qubit TOFFOLI gates, (b) many-qubit FANOUT gates, or (c) mid-circuit measurements with classical feedforward control. Recent advances in quantum computing hardware suggest experimental feasibility of these models in the near future. Our results demonstrate that unitary designs and PRUs can be constructed in much weaker circuit models than previously thought. Furthermore, our construction of PRUs in constant-depth with many-qubit TOFFOLI gates shows that, under cryptographic assumptions, there is no polynomial-time learning algorithm for the circuit class QAC0. Finally, our results suggest a new approach towards proving that PARITY is not computable in QAC0, a long-standing question in quantum complexity theory.