Quantum Information and Computation · 2016 · 53 citations · 0 references
ComputingComputer ScienceCryptographyQuantum ComputingQuantum MechanicsHash FunctionsQuantum BitsQuantum CircuitsQuantum ComputationQuantum GatesQuantum Hardware ArchitecturesCircuit Depth OptimizationElementary Quantum GatesHash Function DesignHash Function ImplementationQuantum Circuit ConstructionQuantum Circuit Depth ReductionQuantum Circuit SynthesisQuantum Gate Synthesis
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 Oe(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).