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.

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

References in corpus (7)

• Experimental Quantum State Tomography of Optical Fields and Ultrafast Statistical Sampling
• Quantum Process Tomography: Resource Analysis of Different Strategies
• Application of a resource theory for magic states to fault-tolerant quantum computing
• Quantum circuits of T-depth one
• Simulation of Qubit Quantum Circuits via Pauli Propagation
• Learning and Testing Algorithms for the Clifford Group
• The Learnability of Quantum States

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