Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2305.15398 · Quantum

Learning t-doped stabilizer states

Lorenzo Leone, Salvatore F. E. Oliviero, Alioscia Hamma

Published May 27, 2024• 42 citations
arXivHTMLPDF

Abstract

In this paper, we present a learning algorithm aimed at learning states obtained from computational basis states by Clifford circuits doped with a finite number t of T -gates. The algorithm learns an exact tomographic description of t -doped stabilizer states in terms of Pauli observables. This is possible because such states are countable and form a discrete set. To tackle the problem, we introduce a novel algebraic framework for t -doped stabilizer states, which extends beyond T -gates and includes doping with any kind of local non-Clifford gate. The algorithm requires resources of complexity poly⁡(n,2t) and exhibits an exponentially small probability of failure.

DOI
10.22331/q-2024-05-27-1361

Related papers

Learning Quantum Circuits of Some T Gates

Ching–Yi Lai, Hao–Chung Cheng

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 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:2106.12524•IEEE Transactions on Information Theory•Feb 15, 2022•35 citations

Efficient learning of Clifford disentanglers and typical $t$-doped unitaries with exponentially more $T$ gates

Gerard Aguilar, Sofiene Jerbi, Jens Eisert +1 more

Highly entangled and highly non-stabilizer quantum states need not be hard to learn. We give efficient algorithms for testing and recovering hidden tensor-product structure in unknown pure state vectors of the form $\lvertψ\rangle = U_C \bigotimes_i \lvertψ_i\rangle$, where $U_C$ is an arbitrary unknown Clifford unitary. Although the Clifford can thoroughly scramble the visible product structure, we prove that the Bell distribution retains a characteristic family of quadratic symmetries. By simultaneously block-diagonalising these symmetries, our algorithms linearize the problem and manage to recover both a disentangling Clifford and the hidden partitions with polynomial sample and computational complexity. This may be viewed as an extension of the abelian StateHSP paradigm in which classical post-processing exposes genuinely quadratic structure. Applied to Choi states, the method yields efficient proper learning algorithms for typical $t$-doped Clifford unitaries in regimes containing exponentially more $T$ gates than previously accessible: the required condition fails only for an exponentially small fraction of circuits when $t\sim n$, and continues to hold for a constant fraction even when $t=2n$. Our framework also provides tools for compressing structured many-body Hamiltonians and suggests benchmarking protocols for encoded logical product states in the early fault-tolerant regime.

quant-pharXiv:2609.27565•Sep 24, 2026•0 citations

Efficient learning of t -doped stabilizer states with single-copy measurements

Nai-Hui Chia, Ching–Yi Lai, Han-Hsuan Lin

One of the primary objectives in the field of quantum state learning is to develop algorithms that are time-efficient for learning states generated from quantum circuits. Earlier investigations have demonstrated time-efficient algorithms for states generated from Clifford circuits with at most log⁡(n) non-Clifford gates. However, these algorithms necessitate multi-copy measurements, posing implementation challenges in the near term due to the requisite quantum memory. On the contrary, using solely single-qubit measurements in the computational basis is insufficient in learning even the output distribution of a Clifford circuit with one additional T gate under reasonable post-quantum cryptographic assumptions. In this work, we introduce an efficient quantum algorithm that employs only nonadaptive single-copy measurement to learn states produced by Clifford circuits with a maximum of O(log⁡n) non-Clifford gates, filling a gap between the previous positive and negative results.

arXiv:2308.07014•Quantum•Feb 12, 2024•14 citations

Efficient Learning of Clifford-Scrambled Product States

Tobias Haug

Clifford circuits acting on product magic states provide a compact ansatz exhibiting extensive magic, volume-law entanglement, and even classically hard sampling under standard complexity assumptions. Here, we efficiently recover its hidden product subsystems from two-copy Bell sampling. Quadratic relations between Bell samples determine the irreducible blocks after removing Pauli stabilizers, and binary linear algebra constructs a Clifford disentangler. For logarithmic-size blocks, approximate learning of the full state is efficient whenever the state remains inverse-polynomially separated from acquiring additional Pauli stabilizers. We efficiently learn $n$-qubit states prepared by random $T$-doped Clifford circuits with $T$-gate density below one via $O(n^2)$ Bell samples, and disentangle hidden product blocks in Clifford-augmented matrix product states. For unitary learning, we exactly learn $T$-depth-one circuits using $O(n^2)$ queries. Finally, we rule out pseudorandom states and unitaries with a product bipartition hidden by Clifford circuits.

quant-pharXiv:2609.27128•Sep 24, 2026•0 citations

Learning quantum circuits of T -depth one

Ching–Yi Lai, Hao–Chung Cheng

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 algorithm to reconstruct its circuit representation by using O(n2) queries to it. It is unknown for decades how to handle circuits beyond the Clifford group for which the stabilizer formalism cannot be applied. Herein, we study quantum circuits of T -depth one on the computational basis. We show that their output states can be represented by a certain stabilizer pseudomixture. By analyzing the algebraic structure of the stabilizer pseudomixture, we can generate a hypothesis circuit that is equivalent to the unknown target T -depth one quantum circuit U on computational basis states, using Pauli and Bell measurements. If the number of T gates in U is of the order O(log n), our algorithm requires O(n2) queries to U to produce its equivalent circuit representation on the computational basis in time O(n3). Using further additional O(43n) classical computations, we can derive an exact description of U for arbitrary input states. Our results greatly extend the previously known facts that stabilizer states can be efficiently identified based on the stabilizer formalism.The full manuscript can be found at [1].

IEEE International Symposium on Information Theory (ISIT)•Jun 26, 2022•0 citations

Adaptivity is all you need: Optimal stabilizer learning using just single-copy measurements

L. Bittel, J. Eisert, W. Gong +2 more

Stabilizer states are central to quantum computing, underlying quantum error correction, benchmarking, and efficient classical simulation. Yet their learnability exhibits a striking gap: an $n$-qubit stabilizer state can be learned from $Θ(n)$ copies using two-copy Bell measurements, whereas non-adaptive single-copy measurements require $Ω(n^2)$ copies. Here we show that adaptivity completely closes this gap. We give a polynomial-time adaptive algorithm that learns an arbitrary $n$-qubit stabilizer state from $Θ(n)$ single-copy Clifford measurements, matching the optimal sample complexity of Bell sampling without any multi-copy measurements. The same ideas yield a sample-optimal single-copy tolerant tester and, with $k$ qubits of quantum memory, the optimal testing tradeoff $Θ(n-k+1/\varepsilon)$ at infidelity $\varepsilon$. Finally, we show that this adaptive mechanism extends beyond exact stabilizer states: states of stabilizer nullity at most $r$, including states prepared by Clifford circuits with a bounded number of $T$ gates, can be learned using $O(n2^{r})$ single-copy measurements.

quant-pharXiv:2610.02031•Oct 2, 2026•0 citations
In this paper, we present a learning algorithm aimed at learning states obtained from computational basis states by Clifford circuits doped with a finite number t of T -gates. The algorithm learns an exact tomographic description of t -doped stabilizer states in terms of Pauli observables. This is possible because such states are countable and form a discrete set. To tackle the problem, we introduce a novel algebraic framework for t -doped stabilizer states, which extends beyond T -gates and includes doping with any kind of local non-Clifford gate. The algorithm requires resources of complexity poly⁡(n,2t) and exhibits an exponentially small probability of failure.
In this paper, we study the problem of learning an unknown quantum circuit of a certain structure. If the unknown target is annnn-qubit Clifford circuit, we devise an efficient algorithm to reconstruct its circuit representation by usingO(n2)O(n^{2})O(n2)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 ofTTT-depth one on the computational basis. We show that the output state of aTTT-depth one circuit 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 ofTTTgates of the target is of the orderO(log⁡n)O({\log n})O(logn), our algorithm requiresO(n2)O(n^{2})O(n2)queries to it and produces its equivalent circuit representation on the computational basis in timeO(n3)O(n^{3})O(n3). Using further additionalO(43n)O(4^{3n})O(43n)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.
Efficient learning of Clifford disentanglers and typical ttt-doped unitaries with exponentially more TTT gates
Highly entangled and highly non-stabilizer quantum states need not be hard to learn. We give efficient algorithms for testing and recovering hidden tensor-product structure in unknown pure state vectors of the form ∣ψ⟩=UC⨂i∣ψi⟩\lvertψ\rangle = U_C \bigotimes_i \lvertψ_i\rangle∣ψ⟩=UC​⨂i​∣ψi​⟩, where UCU_CUC​ is an arbitrary unknown Clifford unitary. Although the Clifford can thoroughly scramble the visible product structure, we prove that the Bell distribution retains a characteristic family of quadratic symmetries. By simultaneously block-diagonalising these symmetries, our algorithms linearize the problem and manage to recover both a disentangling Clifford and the hidden partitions with polynomial sample and computational complexity. This may be viewed as an extension of the abelian StateHSP paradigm in which classical post-processing exposes genuinely quadratic structure. Applied to Choi states, the method yields efficient proper learning algorithms for typical ttt-doped Clifford unitaries in regimes containing exponentially more TTT gates than previously accessible: the required condition fails only for an exponentially small fraction of circuits when t∼nt\sim nt∼n, and continues to hold for a constant fraction even when t=2nt=2nt=2n. Our framework also provides tools for compressing structured many-body Hamiltonians and suggests benchmarking protocols for encoded logical product states in the early fault-tolerant regime.
One of the primary objectives in the field of quantum state learning is to develop algorithms that are time-efficient for learning states generated from quantum circuits. Earlier investigations have demonstrated time-efficient algorithms for states generated from Clifford circuits with at most log⁡(n) non-Clifford gates. However, these algorithms necessitate multi-copy measurements, posing implementation challenges in the near term due to the requisite quantum memory. On the contrary, using solely single-qubit measurements in the computational basis is insufficient in learning even the output distribution of a Clifford circuit with one additional T gate under reasonable post-quantum cryptographic assumptions. In this work, we introduce an efficient quantum algorithm that employs only nonadaptive single-copy measurement to learn states produced by Clifford circuits with a maximum of O(log⁡n) non-Clifford gates, filling a gap between the previous positive and negative results.
Clifford circuits acting on product magic states provide a compact ansatz exhibiting extensive magic, volume-law entanglement, and even classically hard sampling under standard complexity assumptions. Here, we efficiently recover its hidden product subsystems from two-copy Bell sampling. Quadratic relations between Bell samples determine the irreducible blocks after removing Pauli stabilizers, and binary linear algebra constructs a Clifford disentangler. For logarithmic-size blocks, approximate learning of the full state is efficient whenever the state remains inverse-polynomially separated from acquiring additional Pauli stabilizers. We efficiently learn nnn-qubit states prepared by random TTT-doped Clifford circuits with TTT-gate density below one via O(n2)O(n^2)O(n2) Bell samples, and disentangle hidden product blocks in Clifford-augmented matrix product states. For unitary learning, we exactly learn TTT-depth-one circuits using O(n2)O(n^2)O(n2) queries. Finally, we rule out pseudorandom states and unitaries with a product bipartition hidden by Clifford circuits.
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 algorithm to reconstruct its circuit representation by using O(n2) queries to it. It is unknown for decades how to handle circuits beyond the Clifford group for which the stabilizer formalism cannot be applied. Herein, we study quantum circuits of T -depth one on the computational basis. We show that their output states can be represented by a certain stabilizer pseudomixture. By analyzing the algebraic structure of the stabilizer pseudomixture, we can generate a hypothesis circuit that is equivalent to the unknown target T -depth one quantum circuit U on computational basis states, using Pauli and Bell measurements. If the number of T gates in U is of the order O(log n), our algorithm requires O(n2) queries to U to produce its equivalent circuit representation on the computational basis in time O(n3). Using further additional O(43n) classical computations, we can derive an exact description of U for arbitrary input states. Our results greatly extend the previously known facts that stabilizer states can be efficiently identified based on the stabilizer formalism.The full manuscript can be found at [1].
Stabilizer states are central to quantum computing, underlying quantum error correction, benchmarking, and efficient classical simulation. Yet their learnability exhibits a striking gap: an nnn-qubit stabilizer state can be learned from Θ(n)Θ(n)Θ(n) copies using two-copy Bell measurements, whereas non-adaptive single-copy measurements require Ω(n2)Ω(n^2)Ω(n2) copies. Here we show that adaptivity completely closes this gap. We give a polynomial-time adaptive algorithm that learns an arbitrary nnn-qubit stabilizer state from Θ(n)Θ(n)Θ(n) single-copy Clifford measurements, matching the optimal sample complexity of Bell sampling without any multi-copy measurements. The same ideas yield a sample-optimal single-copy tolerant tester and, with kkk qubits of quantum memory, the optimal testing tradeoff Θ(n−k+1/ε)Θ(n-k+1/\varepsilon)Θ(n−k+1/ε) at infidelity ε\varepsilonε. Finally, we show that this adaptive mechanism extends beyond exact stabilizer states: states of stabilizer nullity at most rrr, including states prepared by Clifford circuits with a bounded number of TTT gates, can be learned using O(n2r)O(n2^{r})O(n2r) single-copy measurements.