Simple constructions of linear-depth t-designs and pseudorandom unitaries

Simple constructions of linear-depth t-designs and pseudorandom unitaries

19 Apr 2024 | Tony Metger, Alexander Poremba, Makrand Sinha, and Henry Yuen
This paper presents a unified approach to constructing $t$-designs and pseudorandom unitaries (PRUs) using the "PFC ensemble," which is the product of a random computational basis permutation, a random binary phase operator, and a random Clifford unitary. The key contributions include: 1. **Linear-depth $t$-designs**: The authors provide the first construction of a (diamond-error) approximate $t$-design with circuit depth linear in $t$. This is achieved by replacing the random phase and permutation operators with their $2t$-wise independent counterparts in the PFC ensemble. 2. **Non-adaptive PRUs**: They construct PRUs with non-adaptive security, meaning the unitaries are computationally indistinguishable from Haar random unitaries to polynomial-time distinguishers that query the unitary in parallel on an arbitrary state. This is accomplished by replacing the random phase and permutation operators with their pseudorandom counterparts in the PFC ensemble. 3. **Adaptive Pseudorandom Isometries (PRIs)**: The authors show that a small modification of their PRU construction achieves adaptive security for isometries, i.e., unitaries that map $n$ qubits to $n + \omega(\log n)$ qubits. This is the first construction of adaptive PRIs, and under an additional conjecture, it also extends to adaptive PRUs. The PFC ensemble is analyzed in detail, showing that it reproduces exponentially high moments of the Haar measure. The paper also discusses the implications and potential applications of these constructions in quantum information and computation, including quantum cryptography and modeling chaotic quantum systems.This paper presents a unified approach to constructing $t$-designs and pseudorandom unitaries (PRUs) using the "PFC ensemble," which is the product of a random computational basis permutation, a random binary phase operator, and a random Clifford unitary. The key contributions include: 1. **Linear-depth $t$-designs**: The authors provide the first construction of a (diamond-error) approximate $t$-design with circuit depth linear in $t$. This is achieved by replacing the random phase and permutation operators with their $2t$-wise independent counterparts in the PFC ensemble. 2. **Non-adaptive PRUs**: They construct PRUs with non-adaptive security, meaning the unitaries are computationally indistinguishable from Haar random unitaries to polynomial-time distinguishers that query the unitary in parallel on an arbitrary state. This is accomplished by replacing the random phase and permutation operators with their pseudorandom counterparts in the PFC ensemble. 3. **Adaptive Pseudorandom Isometries (PRIs)**: The authors show that a small modification of their PRU construction achieves adaptive security for isometries, i.e., unitaries that map $n$ qubits to $n + \omega(\log n)$ qubits. This is the first construction of adaptive PRIs, and under an additional conjecture, it also extends to adaptive PRUs. The PFC ensemble is analyzed in detail, showing that it reproduces exponentially high moments of the Haar measure. The paper also discusses the implications and potential applications of these constructions in quantum information and computation, including quantum cryptography and modeling chaotic quantum systems.
Reach us at info@study.space