Related papers: Unitary Channel Testing Under a Depolarizing Noise Assumption

Unitary Channel Testing Under a Depolarizing Noise Assumption

URL: http://arxiv.org/abs/2606.10730v1
Date: Tue, 09 Jun 2026 11:39:34 GMT
Title: Unitary Channel Testing Under a Depolarizing Noise Assumption
Abstract summary: Under the depolarizing noise assumption, often made in quantum computations, we present algorithms to test its strength.<n>Our optimal algorithms answer the following question: is the quantum channel implemented by a given black box identical to a unitary or $varepsilon$far from it in the diamond distance?
Score: 0.3745473778205557
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We present fast algorithms $\unicode{x2013}$ under the depolarizing noise assumption, often made in fault-tolerant quantum computations $\unicode{x2013}$ to test its strength. Our optimal algorithms answer the following question: is the quantum channel implemented by a given black box identical to a target unitary or $\varepsilon$-far from it in the diamond distance, assuming that the deviation is a depolarizing channel with unknown parameter? Our algorithm has a query complexity of $Θ(1/\varepsilon).$ The query complexity of the relaxed problem of testing whether the black-box channel is $\varepsilon_1$-close to a target unitary or $\varepsilon_2$-far in the diamond distance is $Θ\bigl(\varepsilon_2/(\varepsilon_2 - \varepsilon_1)^2\bigr).$ In both cases, we provide matching lower bounds that hold even for adaptive, ancilla-assisted protocols with multi-outcome incoherent measurements.

Related papers

Hardness of High-Dimensional Linear Classification [58.29089693778071]
We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
arXiv Detail & Related papers (2026-03-19T15:53:41Z)
Optimal lower bound for quantum channel tomography in away-from-boundary regime [32.904052887092284]
Heisenberg scaling $(d2/varepsilon)$ is achievable.<n>In particular, this lower bound fully settles the query complexity for the commonly studied case of equal input and output dimensions.
arXiv Detail & Related papers (2026-01-15T18:45:59Z)
Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
arXiv Detail & Related papers (2023-07-13T18:59:28Z)
Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
We explore potential quantum speedups for the fundamental problem of testing the properties of closeness and $k$-wise uniformity of probability distributions. We show that the quantum query complexities for $ell1$- and $ell2$-closeness testing are $O(sqrtn/varepsilon)$ and $O(sqrtnk/varepsilon)$. We propose the first quantum algorithm for this problem with query complexity $O(sqrtnk/varepsilon)
arXiv Detail & Related papers (2023-04-25T15:32:37Z)
Query-optimal estimation of unitary channels in diamond distance [3.087385668501741]
We consider process tomography for unitary quantum channels. We output a classical description of a unitary that is $varepsilon$-close to the unknown unitary in diamond norm.
arXiv Detail & Related papers (2023-02-27T19:00:00Z)
Tight Bounds for Quantum State Certification with Incoherent Measurements [18.566266990940374]
When $sigma$ is the maximally mixed state $frac1d I_d$, this is known as mixedness testing. We focus on algorithms which use incoherent measurements, i.e. which only measure one copy of $rho$ at a time.
arXiv Detail & Related papers (2022-04-14T17:59:31Z)
Random quantum circuits transform local noise into global white noise [118.18170052022323]
We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
arXiv Detail & Related papers (2021-11-29T19:26:28Z)
The Price of Tolerance in Distribution Testing [31.10049510641336]
We show the sample complexity to be [fracsqrtnvarepsilon2 + fracnlog n cdotmaxleftfracvarepsilon2, providing a smooth tradeoff between the two previously known cases. We also provide a similar characterization for the problem of tolerant equivalence testing, where both $p$ and $q$ are unknown.
arXiv Detail & Related papers (2021-06-25T03:59:42Z)
Streaming Complexity of SVMs [110.63976030971106]
We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
arXiv Detail & Related papers (2020-07-07T17:10:00Z)
Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
We find an algorithm which finds. epsilon$-approximate stationary point (with $|nabla F(x)|le epsilon$) using. $(epsilon,gamma)$surimate random random points. Our lower bounds here are novel even in the noiseless case.
arXiv Detail & Related papers (2020-06-24T04:41:43Z)
Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm [100.11971836788437]
We study the fixed-support Wasserstein barycenter problem (FS-WBP) We develop a provably fast textitdeterministic variant of the celebrated iterative Bregman projection (IBP) algorithm, named textscFastIBP.
arXiv Detail & Related papers (2020-02-12T03:40:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.