Quantum certification of state set and unitary channel
- URL: http://arxiv.org/abs/2103.02837v1
- Date: Thu, 4 Mar 2021 05:17:49 GMT
- Title: Quantum certification of state set and unitary channel
- Authors: Wei Xie
- Abstract summary: We study efficient quantum certification algorithms for quantum state set and unitary quantum channel.
We present an algorithm that uses $O(varepsilon-4ln |mathcalP|)$ copies of an unknown state to distinguish whether the unknown state is contained in or $varepsilon$-far from a finite set.
- Score: 2.3889084213601346
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study efficient quantum certification algorithms for quantum state set and
unitary quantum channel. We present an algorithm that uses
$O(\varepsilon^{-4}\ln |\mathcal{P}|)$ copies of an unknown state to
distinguish whether the unknown state is contained in or $\varepsilon$-far from
a finite set $\mathcal{P}$ of known states with respect to the trace distance.
This algorithm is more sample-efficient in some settings. Previous study showed
that one can distinguish whether an unknown unitary $U$ is equal to or
$\varepsilon$-far from a known or unknown unitary $V$ in fixed dimension with
$O(\varepsilon^{-2})$ uses of the unitary, in which the Choi state is used and
thus an ancilla system is needed. We give an algorithm that distinguishes the
two cases with $O(\varepsilon^{-1})$ uses of the unitary, using much fewer or
no ancilla compared with previous results.
Related papers
- Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits [55.957560311008926]
We propose a piecewise stationary linear bandit (PSLB) model where the quality of an arm is measured by its return averaged over all contexts.
PS$varepsilon$BAI$+$ is guaranteed to identify an $varepsilon$-optimal arm with probability $ge 1-delta$ and with a minimal number of samples.
arXiv Detail & Related papers (2024-10-10T06:15:42Z) - Polynomial-time tolerant testing stabilizer states [4.65004369765875]
An algorithm is given copies of an unknown $n$-qubit quantum state $|psirangle promised $(i)$ $|psirangle$.
We show that for every $varepsilon_1>0$ and $varepsilonleq varepsilon_C$, there is a $textsfpoly that decides which is the case.
Our proof includes a new definition of Gowers norm for quantum states, an inverse theorem for the Gowers-$3$ norm of quantum states and new bounds on stabilizer covering for
arXiv Detail & Related papers (2024-08-12T16:56:33Z) - 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) - Improved Stabilizer Estimation via Bell Difference Sampling [0.43123403062068827]
We study the complexity of learning quantum states in various models with respect to the stabilizer formalism.
We prove that $Omega(n)$ $T$gates are necessary for any Clifford+$T$ circuit to prepare pseudorandom quantum states.
We show that a modification of the above algorithm runs in time.
arXiv Detail & Related papers (2023-04-27T01:58:28Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods.
We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
arXiv Detail & Related papers (2023-03-03T18:23:20Z) - Layered State Discovery for Incremental Autonomous Exploration [106.37656068276901]
Layered Autonomous Exploration (LAE) is a novel algorithm for AX that attains a sample complexity of $tildemathcalO(LSrightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightar row_LAln12(Srightarrow_LAln12
arXiv Detail & Related papers (2023-02-07T22:58:12Z) - Ancilla-free certification of unitary quantum processes [2.3889084213601346]
We study efficient quantum certification algorithms for unitary quantum process using no ancilla.
We give an algorithm that distinguishes the two cases with $O(varepsilon-1)$ uses of the unitary, using fewer or no ancilla, outperforming previous relevant results.
arXiv Detail & Related papers (2022-11-28T18:53:11Z) - Quantum Approximation of Normalized Schatten Norms and Applications to
Learning [0.0]
This paper addresses the problem of defining a similarity measure for quantum operations that can be textitefficiently estimated
We develop a quantum sampling circuit to estimate the normalized Schatten 2-norm of their difference and prove a Poly$(frac1epsilon)$ upper bound on the sample complexity.
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.
arXiv Detail & Related papers (2022-06-23T07:12:10Z) - Quantum Algorithm for Fidelity Estimation [8.270684567157987]
For two unknown mixed quantum states $rho$ and $sigma$ in an $N$-dimensional space, computing their fidelity $F(rho,sigma)$ is a basic problem.
We propose a quantum algorithm that solves this problem in $namepoly(log (N), r, 1/varepsilon)$ time.
arXiv Detail & Related papers (2021-03-16T13:57:01Z) - Improved Sample Complexity for Incremental Autonomous Exploration in
MDPs [132.88757893161699]
We learn the set of $epsilon$-optimal goal-conditioned policies attaining all states that are incrementally reachable within $L$ steps.
DisCo is the first algorithm that can return an $epsilon/c_min$-optimal policy for any cost-sensitive shortest-path problem.
arXiv Detail & Related papers (2020-12-29T14:06:09Z) - Locally Private Hypothesis Selection [96.06118559817057]
We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution.
We show that the constraint of local differential privacy incurs an exponential increase in cost.
Our algorithms result in exponential improvements on the round complexity of previous methods.
arXiv Detail & Related papers (2020-02-21T18:30:48Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.