Random quantum circuits are approximate unitary <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>t</mml:mi></mml:math>-designs in depth <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mrow><mml:mi>n</mml:mi><mml:msup><mml:mi>t</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>5</mml:mn><mml:mo>+</mml:mo><mml:mi>o</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:msup></mml:mrow><mml:mo>)</mml:mo></mml:mrow></mml:math>

Jonas Haferkamp

2022Quantum79 citationsDOI Open Access PDF

Abstract

The applications of random quantum circuits range from quantum computing and quantum many-body systems to the physics of black holes. Many of these applications are related to the generation of quantum pseudorandomness: Random quantum circuits are known to approximate unitary <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>t</mml:mi></mml:math>-designs. Unitary <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>t</mml:mi></mml:math>-designs are probability distributions that mimic Haar randomness up to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>t</mml:mi></mml:math>th moments. In a seminal paper, Brandão, Harrow and Horodecki prove that random quantum circuits on qubits in a brickwork architecture of depth <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:msup><mml:mi>t</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>10.5</mml:mn></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math> are approximate unitary <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>t</mml:mi></mml:math>-designs. In this work, we revisit this argument, which lower bounds the spectral gap of moment operators for local random quantum circuits by <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="normal">&#x03A9;</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>&#x2212;</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:msup><mml:mi>t</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>&#x2212;</mml:mo><mml:mn>9.5</mml:mn></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math>. We improve this lower bound to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="normal">&#x03A9;</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>&#x2212;</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup><mml:msup><mml:mi>t</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>&#x2212;</mml:mo><mml:mn>4</mml:mn><mml:mo>&#x2212;</mml:mo><mml:mi>o</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math>, where the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>o</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo></mml:math> term goes to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>0</mml:mn></mml:math> as <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>t</mml:mi><mml:mo stretchy="false">&#x2192;</mml:mo><mml:mi mathvariant="normal">&#x221E;</mml:mi></mml:math>. A direct consequence of this scaling is that random quantum circuits generate approximate unitary <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>t</mml:mi></mml:math>-designs in depth <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:msup><mml:mi>t</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>5</mml:mn><mml:mo>+</mml:mo><mml:mi>o</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math>. Our techniques involve Gao's quantum union bound and the unreasonable effectiveness of the Clifford group. As an auxiliary result, we prove fast convergence to the Haar measure for random Clifford unitaries interleaved with Haar random single qubit unitaries.

Topics & Concepts

Quantum circuitMathematicsUnitary matrixUpper and lower boundsQuantum algorithmQuantumRandomnessDiscrete mathematicsHaar measurePseudorandom number generatorAlgorithmQuantum mechanicsPhysicsUnitary stateQuantum error correctionStatisticsMathematical analysisLawPolitical scienceStochastic Gradient Optimization TechniquesQuantum Computing Algorithms and ArchitectureRandom Matrices and Applications