The role of randomness in quantum computing
Randomness has long been identified as a powerful resource for information processing. Randomized algorithms, for instance, often solve challenging problems substantially faster than fully deterministic ones, while randomness is also an indispensable resource in cryptography. The advent of quantum technologies further augments this already prominent role, because quantum mechanics is a probabilistic theory. This poses novel challenges, but also provides new opportunities.
Accessing quantum information is contingent on measuring the underlying microscopic system. Such measurements necessarily produce random outcomes (Born rule) and often destroys the system (wave function collapse). Meaningful information is stored in outcome distribution, not the outcomes themselves. And many repetitions are required to retrieve this information reliably. This bottleneck is real and often negates potential quantum advantages. Arguably, because of this measurement problem, genuine quantum speedups are much rarer and less spectacular than one might initially expect.
Conversely, injecting additional classical randomness often adds nicely to the underlying quantum randomness. Desirable effects like concentration and convergence to generic problem instances tend to occur much earlier and with much higher confidence. This means that the mathematical toolbox to study randomized quantum algorithms is more powerful (and, arguably, often also easier to apply) than its classical counterpart. To paraphrase, randomization of quantum computing tasks often comes even more naturally than in the classical case.
Our research agenda revolves around identifying situations, where positive aspects of randomness reliably outweigh negative ones. The broad goal is to identify genuine quantum advantages, but also to delineate fundamental no-go theorems. Selected contributions are:
Randomized measurements for efficient quantum to classical conversion (classical shadows)
We present an efficient method for constructing an approximate classical description of a quantum system using randomized quantum measurements. Additional randomization turns out to substantially reduce the cost of converting quantum information into classical information. We prove that the number of measurements is independent of system size and even saturates fundamental lower bounds from information theory. Experiments (both in silico and in vitro) highlight the advantages relative to previously known methods.
Randomized compiling for quantum simulation (Qdrift)
Quantum simulation has wide applications in quantum chemistry and physics. Recently, scientists have begun exploring the use of randomized methods for accelerating quantum simulation. Among them, a simple and powerful technique, called qDRIFT. qDrift is known to generate random product formulas which accurately approximate the ideal evolution when averaged over sufficiently many compilation runs. We prove that a typical realization of the randomized product formula already approximates the ideal time evolution. No averaging is required! The gate complexity is independent of the number of terms in the Hamiltonian, but it depends on the system size and the sum of the interaction strengths in the Hamiltonian. The proofs depend on concentration inequalities for vector and matrix martingales. Numerical experiments confirm our theoretical predictions.
Randomized quantum circuits as toy models for interesting physics behavior (quantum complexity growth)
The concept of quantum complexity has far-reaching implications spanning theoretical computer science, quantum many-body physics, and high energy physics. The complexity of a quantum state is defined as the size of the shortest quantum computation that prepares the state. It is reasonable to expect that the complexity of a quantum state governed by a chaotic many-body Hamiltonian grows linearly with time; however, because it is hard to rule out short-cuts, it is notoriously difficult to derive lower bounds on quantum complexity. To go further, one may study more generic models of complexity growth. We prove that local random quantum circuits generate unitary transformations whose complexity grows linearly for a long time, mirroring the behavior one expects in chaotic quantum systems and verifying conjectures by Brown and Susskind in the context of holography (AdS/CFT duality).
Randomized inputs for detecting errors in reversible circuits (classical bonus result)
We consider error detection via simulation for reversible circuit architectures and prove that reversibility augments the performance of this simple error detection protocol to a considerable degree. A single randomly generated input is guaranteed to unveil a single error with a probability that only depends on the size of the error, not the size of the circuit itself. Empirical studies confirm that this behavior typically extends to multiple errors as well. In conclusion, reversible circuits offer characteristics that reduce masking effects–a desirable feature that is in stark contrast to irreversible circuit architectures.