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:2609.40271

Refined sample complexities from the tomographic rate function

Arick Grootveld, Alexander Maloney, Jason Pollack, Peixue Wu

quant-phcs.ITmath-phmath.PRSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations• Revised Oct 5, 2026 (v2)
v1 · Sep 30, 2026v2 · Oct 5, 2026
arXivHTMLPDF

Abstract

Protocols for quantum state tomography can be characterized either by their sample complexity or by the tomographic rate function that governs the large deviation behaviour of error estimates. We establish a framework for the analysis of covariant protocols which allows us to compare these measures. First, we derive the rate functions for several protocols, including random purification-based protocols and the sample-optimal protocol of Haah et al. These rate functions are expressed in terms of a new family of divergences which includes the reverse sandwiched Rényi divergence and Keyl's annealed quantum relative entropy as special cases. We show that these rate functions obey a strict ordering, even though the sample complexity of each protocol is order optimal. We consider a different version of sample complexity based on Wasserstein distance rather than trace distance, and show that the ordering of the rate functions implies analogous strict inequalities for the Wasserstein-type sample complexity. Thus the tomographic rate function is a more fine-grained indicator of the performance of a tomography protocol than the usual sample complexity.

AI Summary

Quantum tomography protocols can have the same order-optimal trace-distance sample complexity while assigning exponentially different probabilities to incorrect estimates. This paper compares those differences through large-deviation rate functions, defined schematically by $P^n(\sigma\mid\rho)\asymp e^{-nI(\sigma\|\rho)}$, and relates them to sample complexity under a different loss. A framework for covariant tomography combines the large deviations of weak Schur sampling with conditional deviations inside Schur blocks. It yields rate functions for power-weighted pretty-good measurements (PGMs) and the Haah protocol, expressed through a two-parameter divergence family $I_{\beta,\gamma}$. The rates satisfy $I^{\mathrm{PGM}}_\beta=I_{\beta,\beta}\le I^{\mathrm{Haah}}_\beta=I_{\beta,\infty}\le D_R=I^{\mathrm{Keyl}}$, with strict inequalities for some states; both weighted families converge to Keyl’s rate as $\beta\to\infty$. The PGM rate is a reverse sandwiched Rényi divergence and is independent of the unitarily invariant, full-support prior. A rank-adaptive weak-Schur/Hilbert–Schmidt PGM has the same rate when $\operatorname{rank}\sigma\le\operatorname{rank}\rho$, and infinite rate otherwise. For $d=2^m$, the maximally mixed state $\tau$, and normalized quantum Wasserstein distance $\overline W_1=W_1/m$, the paper proves $N_{\mathrm{PGM}}/N_{\mathrm{Keyl}}\ge\varepsilon\log d/32$ when $0<\varepsilon\le1/16$ and $\log(1/\delta)\ge4d^2\log(2d/\varepsilon)$. This uses a quantum Marton inequality for Keyl’s upper bound and a random-purification representation for the Hilbert–Schmidt PGM lower bound. The analysis concerns covariant protocols and asymptotic error exponents. The finite-sample separation is state-specific and requires the stated high-confidence regime. The rate function of a modified Haah protocol is explicitly left open.

No sign of AI-generated textAI use disclosedStrong assumptions
ChatGPT 6 (Astra) was used for proofreading, literature surveys, to assist in the derivations of the properties

Error found: The abstract's Wasserstein-ordering language is broader than the proved result, which compares only raw Hilbert–Schmidt PGM with Keyl at the maximally mixed state under an explicitly very small failure-probability condition. The sample-complexity ratio bound guarantees strict separation only when ε log(d) > 32, although it does establish an asymptotically growing separation for fixed ε.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
36 pages, 2 figures

Related papers

The Optimal Rate Function in Covariant Quantum State Tomography

Arick Grootveld, Alexander Maloney, Jason Pollack +1 more

The problem of quantum tomography is to estimate an unknown quantum state $ρ$ from a measurement of $n$ copies of $ρ$. One can ask which tomography protocol, i.e.\ which choice of multi-copy measurement, gives the best possible estimate of $ρ$. To do so, we characterize tomography protocols by their \emph{rate function}, which governs the exponential rate at which a protocol assigns probability to a particular estimate $σ$ of the true state $ρ$. This rate function is a quantum mechanical generalization of the classical relative entropy between the true state and its estimate, and depends on the choice of protocol. It is bounded by the quantum relative entropy, and we show that this bound is sharp: for any $ρ$ and $σ$ we construct a family of protocols whose rate functions converge to the quantum relative entropy $D(σ\|ρ)$. We consider the family of covariant tomography protocols; these are the basis independent state estimation schemes that assume no prior information about $ρ$ and $σ$. Keyl described a specific tomography protocol based on Schur sampling, and conjectured that among all covariant tomography protocols it has the largest possible rate function for all $σ$ and $ρ$. We prove this conjecture. The resulting rate function is an annealed version of quantum relative entropy, due to the cost of learning the eigenbasis in covariant quantum state tomography.

quant-pharXiv:2606.16948•Jun 16, 2026•1 citation

Optimal Low-Rank Quantum State Tomography with Bounded-Sample Joint Measurements

Ashwin Nayak, Xingyu Zhou

We determine the optimal sample complexity of low-rank quantum state tomography when each measurement may act jointly on at most $t$ samples. For sufficiently small $\varepsilon$, estimating an unknown state on $\mathbb{C}^d$ of rank at most $r$ to trace norm error $\varepsilon$ with constant success probability requires, and is achievable with, $$Θ\left(\frac{dr}{\varepsilon^2}\mathop{\mathrm{max}}\left\{1,\frac{r}{\sqrt{t}}\right\}\right)$$ samples. The lower bound allows the protocol to choose each joint measurement adaptively using all previous classical outcomes; the matching upper bound is nonadaptive. Thus joint measurements on at most $t$ samples improve the complexity of algorithms making single-sample measurements by at most a factor $\sqrt{t}$. Further, measuring order $r^2$ samples jointly is necessary and sufficient to attain the unrestricted collective rate. For the lower bound, we vary the support of a state with fixed uniform spectrum and bound the Fisher information trace of every joint measurement on $t$ samples. The adaptive Fisher chain rule and the van Trees inequality then give the trace norm lower bound. For the upper bound, we construct and analyze a nonadaptive tomography protocol based on a Gaussian joint measurement. An explicit second moment identity and a conditional Gaussian law outside the state's support give a rank-dependent error analysis, yielding the matching rate.

quant-pharXiv:2609.10514•Sep 10, 2026•6 citations

An Optimal Tradeoff between Entanglement and Copy Complexity for State Tomography

Sitan Chen, Jerry Zheng Li, Allen Liu

There has been significant interest in understanding how practical constraints on contemporary quantum devices impact the complexity of quantum learning. For the classic question of tomography, recent work tightly characterized the copy complexity for any protocol that can only measure one copy of the unknown state at a time, showing it is polynomially worse than if one can make fully-entangled measurements. While we now have a fairly complete picture of the rates for such tasks in the near-term and fault-tolerant regimes, it remains poorly understood what the landscape in between these extremes looks like, and in particular how to gracefully scale up our protocols as we transition away from NISQ. In this work, we study tomography in the natural setting where one can make measurements of t copies at a time. For sufficiently small є, we show that for any t ≤ d2, Θ(d3/√tє2) copies are necessary and sufficient to learn an unknown d-dimensional state ρ to trace distance є. This gives a smooth and optimal interpolation between the known rates for single-copy measurements and fully-entangled measurements. To our knowledge, this is the first smooth entanglement-copy tradeoff known for any quantum learning task, and for tomography, no intermediate point on this curve was known, even at t = 2. An important obstacle is that unlike the optimal single-copy protocol, the optimal fully-entangled protocol is inherently a biased estimator. This bias precludes naive batching approaches for interpolating between the two protocols. Instead, we devise a novel two-stage procedure that uses Keyl’s algorithm to refine a crude estimate for ρ based on single-copy measurements. A key insight is to use Schur-Weyl sampling not to estimate the spectrum of ρ, but to estimate the deviation of ρ from the maximally mixed state. When ρ is far from the maximally mixed state, we devise a novel quantum splitting procedure that reduces to the case where ρ is close to maximally mixed.

arXiv:2402.16353•ACM Symposium on Theory of Computing (STOC)•Jun 10, 2024•24 citations

A modified least squares-based tomography with density matrix perturbation and linear entropy consideration along with performance analysis

Subhadeep Mondal, Amit Kumar Dutta

Abstract Quantum state tomography identifies target quantum states by performing repetitive measurements on identical copies. In this paper, we have two key contributions aimed at improving traditional post-processing computational complexity and sample complexity of quantum tomography protocols. In the first case, we propose a new low-cost positivity constraint method based on density matrix perturbation after the least squares (LS) estimation of the density matrix. In the second case, we propose a new cost function with the maximum linear entropy and LS method to improve the sample average trace distance with reasonably low sample complexity. We call it the LS with the maximum entropy (LSME) method. Our proposed algorithm does not follow the iterative optimization technique, which is true for existing maximum likelihood and entropy-based ones. Performance analysis is conducted for our proposed methods by studying how they compare to the existing techniques for different sample complexities and dimensionalities. Extensive numerical simulations have been conducted to demonstrate the advantages of the proposed tomography algorithms.

New Journal of Physics•Aug 1, 2023•6 citations

A Unified Complexity Framework for Quantum Property Testing

Qisheng Wang

We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form $\mathcal{L}_φ(ρ) = \operatorname{tr}(φ(dρ))/d$, where $ρ$ is an unknown $d$-dimensional quantum state and $φ$ is a given function. A master theorem is established that derives sample complexity lower bounds for estimating $\mathcal{L}_φ(ρ)$ from properties of $φ$, combining Haar-random moment encoding with moment matching and best polynomial approximation. Corresponding query complexity lower bounds follow from quantum sample-to-query lifting. The framework yields (nearly) tight bounds for a broad class of problems, including entropy estimation (von Neumann, Rényi, and Tsallis), closeness estimation (trace distance and Uhlmann fidelity), spectrum estimation, rank testing (operator rank, Schmidt rank, and matrix product states). In particular, combined with known upper bounds, we show that the sample complexity of von Neumann entropy estimation is \[ Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)\max\{1, \varepsilon\log^2(d)\}} + \frac{\log^2(d)}{\varepsilon^2}\right), \] and the sample complexity of spectrum estimation is \[ Θ\!\left(\frac{d^2}{\varepsilon^2\log^2(d)\max\{1, \varepsilon^2\log^2(d)\}}\right). \] In summary, our results resolve several open problems and establish the optimality of 37 quantum algorithms since 2015, up to constant or polylogarithmic factors.

quant-pharXiv:2608.02600•Aug 4, 2026•10 citations

Optimal learning of covariant quantum states and channels

Satoshi Yoshida, Kazuki Okigami, Pietro M. Posta +1 more

We give collective tomography protocols for quantum states and channels with known symmetries, using random purification and dilation to reduce learning to pure-state estimation. For states commuting with a compact-group representation with multiplicities $m_λ$, the optimal copy complexity is $Θ((\sum_λm_λ^2+\logη^{-1})/\varepsilon^2)$ for sufficiently small trace-distance error $\varepsilon$ and failure probability $η$ for the nontrivial case $\sum_λm_λ^2>1$. For $G$-covariant channels with finite-dimensional unitary representations of a compact group $G$, parallel $\widetilde{O}(D_G/\varepsilon^2)$ queries achieve a diamond-distance error $\varepsilon $ at fixed success probability $2/3$, where $D_G$ counts the real parameters of covariant Choi operators before imposing trace preservation. For permutation-covariant channels on $k$ qudits of fixed local dimension $d$, at sufficiently small fixed error and fixed success probability $2/3$, we obtain the optimal query scalings $Θ_d(k^{d^4-1})$ for diamond distance and $Θ_d(k^{d^4-d^2})$ for Choi trace distance. Furthermore, we resolve an open problem in quantum tomography of constructing efficient quantum circuits that approximate the Hayashi measurement for optimal pure-state estimation. We encode states in the symmetric subspace into bosonic occupation modes, realize the measurement by heterodyne detection and normalization, and approximate this procedure on qubits using the quantum Hermite transform. Combined with our symmetry-compatible purification and dilation circuits, this yields query-optimal and gate-efficient learners of permutation-covariant states and channels with gate complexity $O_d(\mathrm{poly}(k,\varepsilon^{-1},\logη^{-1}))$.

quant-pharXiv:2609.39280•Oct 1, 2026•0 citations
Protocols for quantum state tomography can be characterized either by their sample complexity or by the tomographic rate function that governs the large deviation behaviour of error estimates. We establish a framework for the analysis of covariant protocols which allows us to compare these measures. First, we derive the rate functions for several protocols, including random purification-based protocols and the sample-optimal protocol of Haah et al. These rate functions are expressed in terms of a new family of divergences which includes the reverse sandwiched Rényi divergence and Keyl's annealed quantum relative entropy as special cases. We show that these rate functions obey a strict ordering, even though the sample complexity of each protocol is order optimal. We consider a different version of sample complexity based on Wasserstein distance rather than trace distance, and show that the ordering of the rate functions implies analogous strict inequalities for the Wasserstein-type sample complexity. Thus the tomographic rate function is a more fine-grained indicator of the performance of a tomography protocol than the usual sample complexity.
Quantum tomography protocols can have the same order-optimal trace-distance sample complexity while assigning exponentially different probabilities to incorrect estimates. This paper compares those differences through large-deviation rate functions, defined schematically by Pn(σ∣ρ)≍e−nI(σ∥ρ)P^n(\sigma\mid\rho)\asymp e^{-nI(\sigma\|\rho)}Pn(σ∣ρ)≍e−nI(σ∥ρ), and relates them to sample complexity under a different loss.
A framework for covariant tomography combines the large deviations of weak Schur sampling with conditional deviations inside Schur blocks. It yields rate functions for power-weighted pretty-good measurements (PGMs) and the Haah protocol, expressed through a two-parameter divergence family Iβ,γI_{\beta,\gamma}Iβ,γ​. The rates satisfy IβPGM=Iβ,β≤IβHaah=Iβ,∞≤DR=IKeylI^{\mathrm{PGM}}_\beta=I_{\beta,\beta}\le I^{\mathrm{Haah}}_\beta=I_{\beta,\infty}\le D_R=I^{\mathrm{Keyl}}IβPGM​=Iβ,β​≤IβHaah​=Iβ,∞​≤DR​=IKeyl, with strict inequalities for some states; both weighted families converge to Keyl’s rate as β→∞\beta\to\inftyβ→∞. The PGM rate is a reverse sandwiched Rényi divergence and is independent of the unitarily invariant, full-support prior. A rank-adaptive weak-Schur/Hilbert–Schmidt PGM has the same rate when rank⁡σ≤rank⁡ρ\operatorname{rank}\sigma\le\operatorname{rank}\rhorankσ≤rankρ, and infinite rate otherwise.
For d=2md=2^md=2m, the maximally mixed state τ\tauτ, and normalized quantum Wasserstein distance W‾1=W1/m\overline W_1=W_1/mW1​=W1​/m, the paper proves NPGM/NKeyl≥εlog⁡d/32N_{\mathrm{PGM}}/N_{\mathrm{Keyl}}\ge\varepsilon\log d/32NPGM​/NKeyl​≥εlogd/32 when 0<ε≤1/160<\varepsilon\le1/160<ε≤1/16 and log⁡(1/δ)≥4d2log⁡(2d/ε)\log(1/\delta)\ge4d^2\log(2d/\varepsilon)log(1/δ)≥4d2log(2d/ε). This uses a quantum Marton inequality for Keyl’s upper bound and a random-purification representation for the Hilbert–Schmidt PGM lower bound.
The analysis concerns covariant protocols and asymptotic error exponents. The finite-sample separation is state-specific and requires the stated high-confidence regime. The rate function of a modified Haah protocol is explicitly left open.
The problem of quantum tomography is to estimate an unknown quantum state ρρρ from a measurement of nnn copies of ρρρ. One can ask which tomography protocol, i.e.\ which choice of multi-copy measurement, gives the best possible estimate of ρρρ. To do so, we characterize tomography protocols by their \emph{rate function}, which governs the exponential rate at which a protocol assigns probability to a particular estimate σσσ of the true state ρρρ. This rate function is a quantum mechanical generalization of the classical relative entropy between the true state and its estimate, and depends on the choice of protocol. It is bounded by the quantum relative entropy, and we show that this bound is sharp: for any ρρρ and σσσ we construct a family of protocols whose rate functions converge to the quantum relative entropy D(σ∥ρ)D(σ\|ρ)D(σ∥ρ). We consider the family of covariant tomography protocols; these are the basis independent state estimation schemes that assume no prior information about ρρρ and σσσ. Keyl described a specific tomography protocol based on Schur sampling, and conjectured that among all covariant tomography protocols it has the largest possible rate function for all σσσ and ρρρ. We prove this conjecture. The resulting rate function is an annealed version of quantum relative entropy, due to the cost of learning the eigenbasis in covariant quantum state tomography.
We determine the optimal sample complexity of low-rank quantum state tomography when each measurement may act jointly on at most ttt samples. For sufficiently small ε\varepsilonε, estimating an unknown state on Cd\mathbb{C}^dCd of rank at most rrr to trace norm error ε\varepsilonε with constant success probability requires, and is achievable with, Θ(drε2max{1,rt})Θ\left(\frac{dr}{\varepsilon^2}\mathop{\mathrm{max}}\left\{1,\frac{r}{\sqrt{t}}\right\}\right)Θ(ε2dr​max{1,t​r​}) samples. The lower bound allows the protocol to choose each joint measurement adaptively using all previous classical outcomes; the matching upper bound is nonadaptive. Thus joint measurements on at most ttt samples improve the complexity of algorithms making single-sample measurements by at most a factor t\sqrt{t}t​. Further, measuring order r2r^2r2 samples jointly is necessary and sufficient to attain the unrestricted collective rate. For the lower bound, we vary the support of a state with fixed uniform spectrum and bound the Fisher information trace of every joint measurement on ttt samples. The adaptive Fisher chain rule and the van Trees inequality then give the trace norm lower bound. For the upper bound, we construct and analyze a nonadaptive tomography protocol based on a Gaussian joint measurement. An explicit second moment identity and a conditional Gaussian law outside the state's support give a rank-dependent error analysis, yielding the matching rate.
There has been significant interest in understanding how practical constraints on contemporary quantum devices impact the complexity of quantum learning. For the classic question of tomography, recent work tightly characterized the copy complexity for any protocol that can only measure one copy of the unknown state at a time, showing it is polynomially worse than if one can make fully-entangled measurements. While we now have a fairly complete picture of the rates for such tasks in the near-term and fault-tolerant regimes, it remains poorly understood what the landscape in between these extremes looks like, and in particular how to gracefully scale up our protocols as we transition away from NISQ. In this work, we study tomography in the natural setting where one can make measurements of t copies at a time. For sufficiently small є, we show that for any t ≤ d2, Θ(d3/√tє2) copies are necessary and sufficient to learn an unknown d-dimensional state ρ to trace distance є. This gives a smooth and optimal interpolation between the known rates for single-copy measurements and fully-entangled measurements. To our knowledge, this is the first smooth entanglement-copy tradeoff known for any quantum learning task, and for tomography, no intermediate point on this curve was known, even at t = 2. An important obstacle is that unlike the optimal single-copy protocol, the optimal fully-entangled protocol is inherently a biased estimator. This bias precludes naive batching approaches for interpolating between the two protocols. Instead, we devise a novel two-stage procedure that uses Keyl’s algorithm to refine a crude estimate for ρ based on single-copy measurements. A key insight is to use Schur-Weyl sampling not to estimate the spectrum of ρ, but to estimate the deviation of ρ from the maximally mixed state. When ρ is far from the maximally mixed state, we devise a novel quantum splitting procedure that reduces to the case where ρ is close to maximally mixed.
Abstract Quantum state tomography identifies target quantum states by performing repetitive measurements on identical copies. In this paper, we have two key contributions aimed at improving traditional post-processing computational complexity and sample complexity of quantum tomography protocols. In the first case, we propose a new low-cost positivity constraint method based on density matrix perturbation after the least squares (LS) estimation of the density matrix. In the second case, we propose a new cost function with the maximum linear entropy and LS method to improve the sample average trace distance with reasonably low sample complexity. We call it the LS with the maximum entropy (LSME) method. Our proposed algorithm does not follow the iterative optimization technique, which is true for existing maximum likelihood and entropy-based ones. Performance analysis is conducted for our proposed methods by studying how they compare to the existing techniques for different sample complexities and dimensionalities. Extensive numerical simulations have been conducted to demonstrate the advantages of the proposed tomography algorithms.
We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form Lφ(ρ)=tr⁡(φ(dρ))/d\mathcal{L}_φ(ρ) = \operatorname{tr}(φ(dρ))/dLφ​(ρ)=tr(φ(dρ))/d, where ρρρ is an unknown ddd-dimensional quantum state and φφφ is a given function. A master theorem is established that derives sample complexity lower bounds for estimating Lφ(ρ)\mathcal{L}_φ(ρ)Lφ​(ρ) from properties of φφφ, combining Haar-random moment encoding with moment matching and best polynomial approximation. Corresponding query complexity lower bounds follow from quantum sample-to-query lifting. The framework yields (nearly) tight bounds for a broad class of problems, including entropy estimation (von Neumann, Rényi, and Tsallis), closeness estimation (trace distance and Uhlmann fidelity), spectrum estimation, rank testing (operator rank, Schmidt rank, and matrix product states). In particular, combined with known upper bounds, we show that the sample complexity of von Neumann entropy estimation is Θ ⁣(d2εlog⁡2(d)max⁡{1,εlog⁡2(d)}+log⁡2(d)ε2), Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)\max\{1, \varepsilon\log^2(d)\}} + \frac{\log^2(d)}{\varepsilon^2}\right), Θ(εlog2(d)max{1,εlog2(d)}d2​+ε2log2(d)​), and the sample complexity of spectrum estimation is Θ ⁣(d2ε2log⁡2(d)max⁡{1,ε2log⁡2(d)}). Θ\!\left(\frac{d^2}{\varepsilon^2\log^2(d)\max\{1, \varepsilon^2\log^2(d)\}}\right). Θ(ε2log2(d)max{1,ε2log2(d)}d2​). In summary, our results resolve several open problems and establish the optimality of 37 quantum algorithms since 2015, up to constant or polylogarithmic factors.
We give collective tomography protocols for quantum states and channels with known symmetries, using random purification and dilation to reduce learning to pure-state estimation. For states commuting with a compact-group representation with multiplicities mλm_λmλ​, the optimal copy complexity is Θ((∑λmλ2+log⁡η−1)/ε2)Θ((\sum_λm_λ^2+\logη^{-1})/\varepsilon^2)Θ((∑λ​mλ2​+logη−1)/ε2) for sufficiently small trace-distance error ε\varepsilonε and failure probability ηηη for the nontrivial case ∑λmλ2>1\sum_λm_λ^2>1∑λ​mλ2​>1. For GGG-covariant channels with finite-dimensional unitary representations of a compact group GGG, parallel O~(DG/ε2)\widetilde{O}(D_G/\varepsilon^2)O(DG​/ε2) queries achieve a diamond-distance error $\varepsilon $ at fixed success probability 2/32/32/3, where DGD_GDG​ counts the real parameters of covariant Choi operators before imposing trace preservation. For permutation-covariant channels on kkk qudits of fixed local dimension ddd, at sufficiently small fixed error and fixed success probability 2/32/32/3, we obtain the optimal query scalings Θd(kd4−1)Θ_d(k^{d^4-1})Θd​(kd4−1) for diamond distance and Θd(kd4−d2)Θ_d(k^{d^4-d^2})Θd​(kd4−d2) for Choi trace distance. Furthermore, we resolve an open problem in quantum tomography of constructing efficient quantum circuits that approximate the Hayashi measurement for optimal pure-state estimation. We encode states in the symmetric subspace into bosonic occupation modes, realize the measurement by heterodyne detection and normalization, and approximate this procedure on qubits using the quantum Hermite transform. Combined with our symmetry-compatible purification and dilation circuits, this yields query-optimal and gate-efficient learners of permutation-covariant states and channels with gate complexity Od(poly(k,ε−1,log⁡η−1))O_d(\mathrm{poly}(k,\varepsilon^{-1},\logη^{-1}))Od​(poly(k,ε−1,logη−1)).