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:2206.11506 · Physical Review A

Quantum approximation of normalized Schatten norms and applications to learning

Yiyou Chen, Hideyuki Miyahara, Louis‐S. Bouchard, Vwani Roychowdhury

Published Nov 9, 2022• 2 citations
arXivHTMLPDF

Abstract

Efficient measures to determine the similarity of quantum states, such as the fidelity metric, have been widely studied. In this paper, we address the problem of defining a similarity measure for quantum operations that can be efficiently estimated. Given two quantum operations, ${U}_{1}$ and ${U}_{2}$, represented in their circuit forms, we first develop a quantum sampling circuit to estimate the normalized Schatten 2-norm of their difference ($\ensuremath{\parallel}{U}_{1}\ensuremath{-}{U}_{2}{\ensuremath{\parallel}}_{{S}_{2}}$) with precision $\ensuremath{\epsilon}$, using only one clean qubit and one classical random variable. We prove a $\text{Poly}(\frac{1}{\ensuremath{\epsilon}})$ upper bound on the sample complexity, which is independent of the size of the quantum system. We then show that such a similarity metric is directly related to a functional definition of similarity of unitary operations using the conventional fidelity metric of quantum states ($\mathcal{F}$): If $\ensuremath{\parallel}{U}_{1}\ensuremath{-}{U}_{2}{\ensuremath{\parallel}}_{{S}_{2}}$ is sufficiently small (e.g., $\ensuremath{\le}\frac{\ensuremath{\epsilon}}{1+\sqrt{2(1/\ensuremath{\delta}\ensuremath{-}1)}}$) then the fidelity of states obtained by processing the same randomly and uniformly picked pure state $|\ensuremath{\psi}\ensuremath{\rangle}$ is as high as needed $[\mathcal{F}({U}_{1}|\ensuremath{\psi}\ensuremath{\rangle},{U}_{2}|\ensuremath{\psi}\ensuremath{\rangle})\ensuremath{\ge}1\ensuremath{-}\ensuremath{\epsilon}]$ with probability exceeding $1\ensuremath{-}\ensuremath{\delta}$. We provide example applications of this efficient similarity metric estimation framework to quantum circuit learning tasks, such as finding the square root of a given unitary operation.

DOI
10.1103/physreva.106.052409

Related papers

The Quantum Complexity of Computing Schatten ppp-norms

Chris Cade, Ashley Montanaro

We consider the quantum complexity of computing Schatten p-norms and related quantities, and find that the problem of estimating these quantities is closely related to the one clean qubit model of computation. We show that the problem of approximating Tr(|A|^p) for a log-local n-qubit Hamiltonian A and p=poly(n), up to a suitable level of accuracy, is contained in DQC1; and that approximating this quantity up to a somewhat higher level of accuracy is DQC1-hard. In some cases the level of accuracy achieved by the quantum algorithm is substantially better than a natural classical algorithm for the problem. The same problem can be solved for arbitrary sparse matrices in BQP. One application of the algorithm is the approximate computation of the energy of a graph.

arXiv:1706.09279•Leibniz international proceedings in informatics•Jun 28, 2017•9 citations

On estimating operator norm distance, with optimal trace distance estimation when one state is pure

Yupan Liu, Qisheng Wang, Zhan Yu

We investigate the computational complexity of estimating the operator norm distance ${\rm T}_{\infty}(ρ_0,ρ_1)$, defined via the operator norm $\|A\|_{\infty} = σ_{\max}(A)$, given ${\rm poly}(n)$-size state-preparation circuits of $n$-qubit quantum states $ρ_0$ and $ρ_1$. We provide efficient quantum estimators for the operator norm distance whose complexity is independent of the rank (and thus the dimension) of the states: 1. When one state is pure, we establish an optimal quantum estimator using $Θ(1/ε)$ queries to the state-preparation circuits. Consequently, for constant additive error, say $ε=1/5$, our estimator runs in ${\rm poly}(n)$ time. Since the operator norm distance ${\rm T}_{\infty}(|ψ\rangle\!\langleψ|,ρ)$ is exactly half of the trace distance ${\rm T}(|ψ\rangle\!\langleψ|,ρ)$, our result also gives rank-independent query complexity for estimating both quantities, whereas the approaches due to van Apeldoorn, Cornelissen, Gily{é}n, and Nannicini (SODA 2023) and Wang and Zhang (TIT 2024) have query complexity scaling at least linearly with ${\rm rank}(ρ)$, which can be $\exp(n)$ in general. 2. For general quantum states, we also provide a quantum estimator using $\widetilde{O}(1/ε^{3/2})$ queries to the state-preparation circuits, which shows that the corresponding promise problem is ${\sf BQP}$-complete and improves the ${\sf QMA}$ upper bound sketched by Liu and Wang (ESA 2025). Together with an $Ω(1/ε)$ quantum query complexity lower bound, this leaves only square-root room for improvement. The key intuition behind our estimators is that, when one state is pure, the pure state $|ψ\rangle$ has overlap at least $1/2$ with the top unit eigenvector of $|ψ\rangle\!\langleψ|-ρ$, reflecting a structural feature specific to the operator norm distance.

quant-pharXiv:2607.03905•Leibniz international proceedings in informatics•Jul 7, 2026•0 citations

The Quantum Complexity of Computing Schatten p-norms

Chris Cade, Ashley Montanaro

We consider the quantum complexity of computing Schatten p-norms and related quantities, and find that the problem of estimating these quantities is closely related to the one clean qubit model of computation. We show that the problem of approximating Tr(|A|^p) for a log-local n-qubit Hamiltonian A and p=poly(n), up to a suitable level of accuracy, is contained in DQC1; and that approximating this quantity up to a somewhat higher level of accuracy is DQC1-hard. In some cases the level of accuracy achieved by the quantum algorithm is substantially better than a natural classical algorithm for the problem. The same problem can be solved for arbitrary sparse matrices in BQP. One application of the algorithm is the approximate computation of the energy of a graph.

Conference on Theory of Quantum Computation, Communication and Cryptography•Jul 1, 2018•6 citations

Fidelity Estimation to a Known Quantum State Is Nearly Quadratic in the Smaller Rank

Gye Jin Lee, Sunghyeon Jo

We study the number of copies needed to estimate the root Uhlmann fidelity between an unknown quantum state and a classically known reference, under collective measurements. If the unknown state has rank at most $s$, we give an estimator using $O(s^2/\varepsilon^2)$ copies, uniformly in the ambient dimension and reference rank. The estimator applies a random-purification channel and a covariant pure-state measurement, then rescales the observed amplitude before evaluating a weighted nuclear norm. Combined with the lower bound established independently in our first version and in concurrent work of Wang, this determines the worst-case complexity under rank bounds $r,s$ as $\min\{r,s\}^2/\varepsilon^2$ up to logarithmic factors in the smaller rank. The same estimator gives the upper bound $O(r(\operatorname{tr}\sqrtσ)^2/\varepsilon^2)$ for a rank-$r$ reference $σ$. We combine spectral truncation with lower bounds obtained by embedding hard instances for the maximally mixed reference into spectral subspaces. For spectra $λ_i\propto i^{-α}$ with fixed $1<α\le2$, as $\varepsilon\downarrow0$ with $r\ge C_α\varepsilon^{-2/(α-1)}$, the bounds determine the complexity as $\widetildeΘ_α(\varepsilon^{-4/(α-1)})$. In particular, inverse-square spectra have accuracy exponent four. The lower-bound construction uses exact moment matching and an explicitly computable Schur measure.

quant-pharXiv:2608.01770•Aug 4, 2026•0 citations

Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of Random Circuit Sampling

Ramis Movassagh

One-parameter interpolations between any two unitary matrices (e.g., quantum gates) $U_1$ and $U_2$ along efficient paths contained in the unitary group are constructed. Motivated by applications, we propose the continuous unitary path $U(θ)$ obtained from the QR-factorization \[ U(θ)R(θ)=(1-θ)A+θB, \] where $U_1 R_1=A$ and $U_2 R_2=B$ are the QR-factorizations of $A$ and $B$, and $U(θ)$ is a unitary for all $θ$ with $U(0)=U_1$ and $U(1)=U_2$. The QR-algorithm is modified to, instead of $U(θ)$, output a matrix whose columns are proportional to the corresponding columns of $U(θ)$ and whose entries are polynomial or rational functions of $θ$. By an extension of the Berlekamp-Welch algorithm we show that rational functions can be efficiently and exactly interpolated with respect to $θ$. We then construct probability distributions over unitaries that are arbitrarily close to the Haar measure. Demonstration of computational advantages of NISQ over classical computers is an imperative near-term goal, especially with the exuberant experimental frontier in academia and industry (e.g., IBM and Google). A candidate for quantum computational supremacy is Random Circuit Sampling (RCS), which is the task of sampling from the output distribution of a random circuit. The aforementioned mathematical results provide a new way of scrambling quantum circuits and are applied to prove that exact RCS is $\#P$-Hard on average, which is a simpler alternative to Bouland et al's. (Dis)Proving the quantum supremacy conjecture requires "approximate" average case hardness; this remains an open problem for all quantum supremacy proposals.

arXiv:1810.04681•Oct 10, 2018•13 citations

Exploring Quantum Average-Case Distances: Proofs, Properties, and Examples

Filip B. Maciejewski, Zbigniew Puchała, Michał Oszmaniec

In this work, we present an in-depth study of average-case quantum distances introduced in Maciejewski et al. (2022). The average-case distances approximate, up to the relative error, the average Total-Variation (TV) distance between measurement outputs of two quantum processes, in which quantum objects of interest (states, measurements, or channels) are intertwined with random quantum circuits. Contrary to conventional distances, such as trace distance or diamond norm, they quantifyaverage-casestatistical distinguishability via random quantum circuits. We prove that once a family of random circuits forms an$\delta $-approximate 4-design, with$\delta =o(d^{-8})$, then the average-case distances can be approximated by simple explicit functions that can be expressed via simple degree two polynomials in objects of interest. For systems of moderate dimension, they can be easily explicitly computed – no optimization is needed as opposed to diamond norm distance between channels or operational distance between measurements. We prove that those functions, which we call quantum average-case distances, have a plethora of desirable properties, such as subadditivity w.r.t. tensor products, joint convexity, and (restricted) data-processing inequalities. Notably, all distances utilize the Hilbert-Schmidt (HS) norm, which provides this norm with a new operational interpretation. We also provide upper bounds on the maximal ratio between worst-case and average-case distances, and for each of them, we provide an example that saturates the bound. Specifically, we show that for each dimension$d$this ratio is at most$d^{\frac {1}{2}}, d, d^{\frac {3}{2}}$for states, measurements, and channels, respectively. To support the practical usefulness of our findings, we study multiple examples in which average-case quantum distances can be calculated analytically.

arXiv:2112.14284•IEEE Transactions on Information Theory•Mar 9, 2023•8 citations
Efficient measures to determine the similarity of quantum states, such as the fidelity metric, have been widely studied. In this paper, we address the problem of defining a similarity measure for quantum operations that can be efficiently estimated. Given two quantum operations, U1{U}_{1}U1​ and U2{U}_{2}U2​, represented in their circuit forms, we first develop a quantum sampling circuit to estimate the normalized Schatten 2-norm of their difference (\ensuremath∥U1\ensuremath−U2\ensuremath∥S2\ensuremath{\parallel}{U}_{1}\ensuremath{-}{U}_{2}{\ensuremath{\parallel}}_{{S}_{2}}\ensuremath∥U1​\ensuremath−U2​\ensuremath∥S2​​) with precision \ensuremathϵ\ensuremath{\epsilon}\ensuremathϵ, using only one clean qubit and one classical random variable. We prove a Poly(1\ensuremathϵ)\text{Poly}(\frac{1}{\ensuremath{\epsilon}})Poly(\ensuremathϵ1​) upper bound on the sample complexity, which is independent of the size of the quantum system. We then show that such a similarity metric is directly related to a functional definition of similarity of unitary operations using the conventional fidelity metric of quantum states (F\mathcal{F}F): If \ensuremath∥U1\ensuremath−U2\ensuremath∥S2\ensuremath{\parallel}{U}_{1}\ensuremath{-}{U}_{2}{\ensuremath{\parallel}}_{{S}_{2}}\ensuremath∥U1​\ensuremath−U2​\ensuremath∥S2​​ is sufficiently small (e.g., \ensuremath≤\ensuremathϵ1+2(1/\ensuremathδ\ensuremath−1)\ensuremath{\le}\frac{\ensuremath{\epsilon}}{1+\sqrt{2(1/\ensuremath{\delta}\ensuremath{-}1)}}\ensuremath≤1+2(1/\ensuremathδ\ensuremath−1)​\ensuremathϵ​) then the fidelity of states obtained by processing the same randomly and uniformly picked pure state ∣\ensuremathψ\ensuremath⟩|\ensuremath{\psi}\ensuremath{\rangle}∣\ensuremathψ\ensuremath⟩ is as high as needed [F(U1∣\ensuremathψ\ensuremath⟩,U2∣\ensuremathψ\ensuremath⟩)\ensuremath≥1\ensuremath−\ensuremathϵ][\mathcal{F}({U}_{1}|\ensuremath{\psi}\ensuremath{\rangle},{U}_{2}|\ensuremath{\psi}\ensuremath{\rangle})\ensuremath{\ge}1\ensuremath{-}\ensuremath{\epsilon}][F(U1​∣\ensuremathψ\ensuremath⟩,U2​∣\ensuremathψ\ensuremath⟩)\ensuremath≥1\ensuremath−\ensuremathϵ] with probability exceeding 1\ensuremath−\ensuremathδ1\ensuremath{-}\ensuremath{\delta}1\ensuremath−\ensuremathδ. We provide example applications of this efficient similarity metric estimation framework to quantum circuit learning tasks, such as finding the square root of a given unitary operation.
We consider the quantum complexity of computing Schatten p-norms and related quantities, and find that the problem of estimating these quantities is closely related to the one clean qubit model of computation. We show that the problem of approximating Tr(|A|^p) for a log-local n-qubit Hamiltonian A and p=poly(n), up to a suitable level of accuracy, is contained in DQC1; and that approximating this quantity up to a somewhat higher level of accuracy is DQC1-hard. In some cases the level of accuracy achieved by the quantum algorithm is substantially better than a natural classical algorithm for the problem. The same problem can be solved for arbitrary sparse matrices in BQP. One application of the algorithm is the approximate computation of the energy of a graph.
We investigate the computational complexity of estimating the operator norm distance T∞(ρ0,ρ1){\rm T}_{\infty}(ρ_0,ρ_1)T∞​(ρ0​,ρ1​), defined via the operator norm ∥A∥∞=σmax⁡(A)\|A\|_{\infty} = σ_{\max}(A)∥A∥∞​=σmax​(A), given poly(n){\rm poly}(n)poly(n)-size state-preparation circuits of nnn-qubit quantum states ρ0ρ_0ρ0​ and ρ1ρ_1ρ1​. We provide efficient quantum estimators for the operator norm distance whose complexity is independent of the rank (and thus the dimension) of the states: 1. When one state is pure, we establish an optimal quantum estimator using Θ(1/ε)Θ(1/ε)Θ(1/ε) queries to the state-preparation circuits. Consequently, for constant additive error, say ε=1/5ε=1/5ε=1/5, our estimator runs in poly(n){\rm poly}(n)poly(n) time. Since the operator norm distance T∞(∣ψ⟩ ⁣⟨ψ∣,ρ){\rm T}_{\infty}(|ψ\rangle\!\langleψ|,ρ)T∞​(∣ψ⟩⟨ψ∣,ρ) is exactly half of the trace distance T(∣ψ⟩ ⁣⟨ψ∣,ρ){\rm T}(|ψ\rangle\!\langleψ|,ρ)T(∣ψ⟩⟨ψ∣,ρ), our result also gives rank-independent query complexity for estimating both quantities, whereas the approaches due to van Apeldoorn, Cornelissen, Gily{é}n, and Nannicini (SODA 2023) and Wang and Zhang (TIT 2024) have query complexity scaling at least linearly with rank(ρ){\rm rank}(ρ)rank(ρ), which can be exp⁡(n)\exp(n)exp(n) in general. 2. For general quantum states, we also provide a quantum estimator using O~(1/ε3/2)\widetilde{O}(1/ε^{3/2})O(1/ε3/2) queries to the state-preparation circuits, which shows that the corresponding promise problem is BQP{\sf BQP}BQP-complete and improves the QMA{\sf QMA}QMA upper bound sketched by Liu and Wang (ESA 2025). Together with an Ω(1/ε)Ω(1/ε)Ω(1/ε) quantum query complexity lower bound, this leaves only square-root room for improvement. The key intuition behind our estimators is that, when one state is pure, the pure state ∣ψ⟩|ψ\rangle∣ψ⟩ has overlap at least 1/21/21/2 with the top unit eigenvector of ∣ψ⟩ ⁣⟨ψ∣−ρ|ψ\rangle\!\langleψ|-ρ∣ψ⟩⟨ψ∣−ρ, reflecting a structural feature specific to the operator norm distance.
We consider the quantum complexity of computing Schatten p-norms and related quantities, and find that the problem of estimating these quantities is closely related to the one clean qubit model of computation. We show that the problem of approximating Tr(|A|^p) for a log-local n-qubit Hamiltonian A and p=poly(n), up to a suitable level of accuracy, is contained in DQC1; and that approximating this quantity up to a somewhat higher level of accuracy is DQC1-hard. In some cases the level of accuracy achieved by the quantum algorithm is substantially better than a natural classical algorithm for the problem. The same problem can be solved for arbitrary sparse matrices in BQP. One application of the algorithm is the approximate computation of the energy of a graph.
We study the number of copies needed to estimate the root Uhlmann fidelity between an unknown quantum state and a classically known reference, under collective measurements. If the unknown state has rank at most sss, we give an estimator using O(s2/ε2)O(s^2/\varepsilon^2)O(s2/ε2) copies, uniformly in the ambient dimension and reference rank. The estimator applies a random-purification channel and a covariant pure-state measurement, then rescales the observed amplitude before evaluating a weighted nuclear norm. Combined with the lower bound established independently in our first version and in concurrent work of Wang, this determines the worst-case complexity under rank bounds r,sr,sr,s as min⁡{r,s}2/ε2\min\{r,s\}^2/\varepsilon^2min{r,s}2/ε2 up to logarithmic factors in the smaller rank. The same estimator gives the upper bound O(r(tr⁡σ)2/ε2)O(r(\operatorname{tr}\sqrtσ)^2/\varepsilon^2)O(r(trσ​)2/ε2) for a rank-rrr reference σσσ. We combine spectral truncation with lower bounds obtained by embedding hard instances for the maximally mixed reference into spectral subspaces. For spectra λi∝i−αλ_i\propto i^{-α}λi​∝i−α with fixed 1<α≤21<α\le21<α≤2, as ε↓0\varepsilon\downarrow0ε↓0 with r≥Cαε−2/(α−1)r\ge C_α\varepsilon^{-2/(α-1)}r≥Cα​ε−2/(α−1), the bounds determine the complexity as Θ~α(ε−4/(α−1))\widetildeΘ_α(\varepsilon^{-4/(α-1)})Θα​(ε−4/(α−1)). In particular, inverse-square spectra have accuracy exponent four. The lower-bound construction uses exact moment matching and an explicitly computable Schur measure.
One-parameter interpolations between any two unitary matrices (e.g., quantum gates) U1U_1U1​ and U2U_2U2​ along efficient paths contained in the unitary group are constructed. Motivated by applications, we propose the continuous unitary path U(θ)U(θ)U(θ) obtained from the QR-factorization U(θ)R(θ)=(1−θ)A+θB, U(θ)R(θ)=(1-θ)A+θB, U(θ)R(θ)=(1−θ)A+θB, where U1R1=AU_1 R_1=AU1​R1​=A and U2R2=BU_2 R_2=BU2​R2​=B are the QR-factorizations of AAA and BBB, and U(θ)U(θ)U(θ) is a unitary for all θθθ with U(0)=U1U(0)=U_1U(0)=U1​ and U(1)=U2U(1)=U_2U(1)=U2​. The QR-algorithm is modified to, instead of U(θ)U(θ)U(θ), output a matrix whose columns are proportional to the corresponding columns of U(θ)U(θ)U(θ) and whose entries are polynomial or rational functions of θθθ. By an extension of the Berlekamp-Welch algorithm we show that rational functions can be efficiently and exactly interpolated with respect to θθθ. We then construct probability distributions over unitaries that are arbitrarily close to the Haar measure. Demonstration of computational advantages of NISQ over classical computers is an imperative near-term goal, especially with the exuberant experimental frontier in academia and industry (e.g., IBM and Google). A candidate for quantum computational supremacy is Random Circuit Sampling (RCS), which is the task of sampling from the output distribution of a random circuit. The aforementioned mathematical results provide a new way of scrambling quantum circuits and are applied to prove that exact RCS is #P\#P#P-Hard on average, which is a simpler alternative to Bouland et al's. (Dis)Proving the quantum supremacy conjecture requires "approximate" average case hardness; this remains an open problem for all quantum supremacy proposals.
In this work, we present an in-depth study of average-case quantum distances introduced in Maciejewski et al. (2022). The average-case distances approximate, up to the relative error, the average Total-Variation (TV) distance between measurement outputs of two quantum processes, in which quantum objects of interest (states, measurements, or channels) are intertwined with random quantum circuits. Contrary to conventional distances, such as trace distance or diamond norm, they quantifyaverage-casestatistical distinguishability via random quantum circuits. We prove that once a family of random circuits forms an$\delta −approximate4−design,with-approximate 4-design, with−approximate4−design,with\delta =o(d^{-8}),thentheaverage−casedistancescanbeapproximatedbysimpleexplicitfunctionsthatcanbeexpressedviasimpledegreetwopolynomialsinobjectsofinterest.Forsystemsofmoderatedimension,theycanbeeasilyexplicitlycomputed–nooptimizationisneededasopposedtodiamondnormdistancebetweenchannelsoroperationaldistancebetweenmeasurements.Weprovethatthosefunctions,whichwecallquantumaverage−casedistances,haveaplethoraofdesirableproperties,suchassubadditivityw.r.t.tensorproducts,jointconvexity,and(restricted)data−processinginequalities.Notably,alldistancesutilizetheHilbert−Schmidt(HS)norm,whichprovidesthisnormwithanewoperationalinterpretation.Wealsoprovideupperboundsonthemaximalratiobetweenworst−caseandaverage−casedistances,andforeachofthem,weprovideanexamplethatsaturatesthebound.Specifically,weshowthatforeachdimension, then the average-case distances can be approximated by simple explicit functions that can be expressed via simple degree two polynomials in objects of interest. For systems of moderate dimension, they can be easily explicitly computed – no optimization is needed as opposed to diamond norm distance between channels or operational distance between measurements. We prove that those functions, which we call quantum average-case distances, have a plethora of desirable properties, such as subadditivity w.r.t. tensor products, joint convexity, and (restricted) data-processing inequalities. Notably, all distances utilize the Hilbert-Schmidt (HS) norm, which provides this norm with a new operational interpretation. We also provide upper bounds on the maximal ratio between worst-case and average-case distances, and for each of them, we provide an example that saturates the bound. Specifically, we show that for each dimension,thentheaverage−casedistancescanbeapproximatedbysimpleexplicitfunctionsthatcanbeexpressedviasimpledegreetwopolynomialsinobjectsofinterest.Forsystemsofmoderatedimension,theycanbeeasilyexplicitlycomputed–nooptimizationisneededasopposedtodiamondnormdistancebetweenchannelsoroperationaldistancebetweenmeasurements.Weprovethatthosefunctions,whichwecallquantumaverage−casedistances,haveaplethoraofdesirableproperties,suchassubadditivityw.r.t.tensorproducts,jointconvexity,and(restricted)data−processinginequalities.Notably,alldistancesutilizetheHilbert−Schmidt(HS)norm,whichprovidesthisnormwithanewoperationalinterpretation.Wealsoprovideupperboundsonthemaximalratiobetweenworst−caseandaverage−casedistances,andforeachofthem,weprovideanexamplethatsaturatesthebound.Specifically,weshowthatforeachdimensiondthisratioisatmostthis ratio is at mostthisratioisatmostd^{\frac {1}{2}}, d, d^{\frac {3}{2}}$for states, measurements, and channels, respectively. To support the practical usefulness of our findings, we study multiple examples in which average-case quantum distances can be calculated analytically.