Near-linear constructions of exact unitary 2-designs
arXiv:1501.04592
Abstract
A unitary 2-design can be viewed as a quantum analogue of a 2-universal hash function: it is indistinguishable from a truly random unitary by any procedure that queries it twice. We show that exact unitary 2-designs on n qubits can be implemented by quantum circuits consisting of ~O(n) elementary gates in logarithmic depth. This is essentially a quadratic improvement in size (and in width times depth) over all previous implementations that are exact or approximate (for sufficiently strong approximations).
arXiv comment30 pages, 10 figures, presentation improved
References in corpus (15)
- Mixed State Entanglement and Quantum Error Correction
- Improved Simulation of Stabilizer Circuits
- A Theory of Fault-Tolerant Quantum Computation
- The capacity of the noisy quantum channel
- Exact and Approximate Unitary 2-Designs: Constructions and Applications
- Superadditivity of communication capacity using entangled inputs
- Evenly distributed unitaries: on the structure of unitary designs
- Randomizing quantum states: Constructions and applications
- Random Quantum Circuits are Approximate 2-designs
- Random Quantum Circuits and Pseudo-Random Operators: Theory and Applications
- A decoupling approach to the quantum capacity
- Choi's Proof and Quantum Process Tomography
- Decoupling with random quantum circuits
- Unconditionally Secure Key Distribution In Higher Dimensions By Depolarization
- Decoupling with unitary approximate two-designs
Cited by in corpus (9)
- Fault-Tolerant Logical Gates in the IBM Quantum Experience
- Approaches for approximate additivity of the Holevo information of quantum channels
- Decoupling with random quantum circuits
- The Clifford group fails gracefully to be a unitary 4-design
- Unitary -designs from random - and -diagonal unitaries
- Derandomizing quantum circuits with measurement based unitary designs
- Efficient methods for one-shot quantum communication
- Maximum privacy without coherence, zero-error
- Charge-conserving unitaries typically generate optimal covariant quantum error-correcting codes