Learning quantum circuits of some $T$ gates

Abstract

In this paper, we study the problem of learning an unknown quantum circuit of a certain structure. If the unknown target is an $n$-qubit Clifford circuit, we devise an efficient algorithm to reconstruct its circuit representation by using $O(n^2)$ queries to it. For decades, it has been unknown how to handle circuits beyond the Clifford group since the stabilizer formalism cannot be applied in this case. Herein, we study quantum circuits of $T$-depth one on the computational basis. We show that the output state of a $T$-depth one circuit {\textit{of full $T$-rank}} can be represented by a stabilizer pseudomixture with a specific algebraic structure. Using Pauli and Bell measurements on copies of the output states, we can generate a hypothesis circuit that is equivalent to the unknown target circuit on computational basis states as input. If the number of $T$ gates of the target is of the order $O(\log n)$, our algorithm requires $O(n^2)$ queries to it and produces its equivalent circuit representation on the computational basis in time $O(n^3)$. Using further additional $O(4^{3n})$ classical computations, we can derive an exact description of the target for arbitrary input states. Our results greatly extend the previously known facts that stabilizer states can be efficiently identified based on the stabilizer formalism.

arXiv comment14 pages, 7 figures. The notion $T$-rank is introduced. Lemma 13 has been modified. Several related statements are revised

References in corpus (32)

• Quantum Teleportation is a Universal Computational Primitive
• Improved Simulation of Stabilizer Circuits
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• A Theory of Fault-Tolerant Quantum Computation
• Experimental Quantum State Tomography of Optical Fields and Ultrafast Statistical Sampling
• Prescription for experimental determination of the dynamics of a quantum black box
• Unknown Quantum States and Operations, a Bayesian View
• Complete Characterization of a Quantum Process: the Two-Bit Quantum Gate
• Quantum state estimation
• Instantaneous non-local computation of low T-depth quantum circuits
• The Heisenberg Representation of Quantum Computers
• Quantum Process Tomography: Resource Analysis of Different Strategies
• Application of a resource theory for magic states to fault-tolerant quantum computing
• Quantum codes on a lattice with boundary
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Practical characterization of quantum devices without tomography
• Trading classical and quantum computational resources
• Quantum circuits of T-depth one
• Quantum Tomography
• The Clifford group, stabilizer states, and linear and quadratic operations over GF(2)
• Sample-optimal tomography of quantum states
• Simulation of Qubit Quantum Circuits via Pauli Propagation
• Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations
• Learning and Testing Algorithms for the Clifford Group
• Pseudo-dimension of quantum circuits
• Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle)
• Complex conjugation supermap of unitary quantum maps and its universal implementation protocol
• The Learnability of Quantum States
• On the Need for Large Quantum Depth
• Constant depth fault-tolerant Clifford circuits for multi-qubit large block codes
• Predicting Features of Quantum Systems from Very Few Measurements
• The Encoding and Decoding Complexities of Entanglement-Assisted Quantum Stabilizer Codes

Cited by in corpus (24)

• Efficient quantum algorithms for stabilizer entropies
• Learning t-doped stabilizer states
• Learning efficient decoders for quasi-chaotic quantum scramblers
• Unscrambling Quantum Information with Clifford decoders
• Learning quantum states and unitaries of bounded gate complexity
• A single $T$-gate makes distribution learning hard
• Bell sampling from quantum circuits
• Learning shallow quantum circuits
• Improved Stabilizer Estimation via Bell Difference Sampling
• Efficient mutual magic and magic capacity with matrix product states
• Efficient learning of $t$-doped stabilizer states with single-copy measurements
• Stabilizer Testing and Magic Entropy via Quantum Fourier Analysis
• Stabilizer Rényi Entropy and Conformal Field Theory
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits
• Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates
• Non-stabilizerness of Neural Quantum States
• Learning Quantum Processes with Quantum Statistical Queries
• Learning unitaries with quantum statistical queries
• Single-copy stabilizer testing
• Clifford Circuits can be Properly PAC Learned if and only if $\text{RP}=\text{NP}$
• Agnostic Process Tomography
• Robust projective measurements through measuring code-inspired observables
• Pseudoentanglement Ain't Cheap
• Process Tomography for Clifford Unitaries