Agnostic Tomography of Stabilizer Product States

• URL: http://arxiv.org/abs/2404.03813v2
• Date: Tue, 08 Oct 2024 06:05:48 GMT
• Title: Agnostic Tomography of Stabilizer Product States
• Authors: Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang,
• Abstract summary: We give an efficient agnostic tomography algorithm for the class $mathcalC$ of $n$-qubit stabilizer product states. We output a succinct description of a state that approximates at least as well as any state in $mathcalC$.
• Score: 0.43123403062068827
• License:
• Abstract: We define a quantum learning task called agnostic tomography, where given copies of an arbitrary state $\rho$ and a class of quantum states $\mathcal{C}$, the goal is to output a succinct description of a state that approximates $\rho$ at least as well as any state in $\mathcal{C}$ (up to some small error $\varepsilon$). This task generalizes ordinary quantum tomography of states in $\mathcal{C}$ and is more challenging because the learning algorithm must be robust to perturbations of $\rho$. We give an efficient agnostic tomography algorithm for the class $\mathcal{C}$ of $n$-qubit stabilizer product states. Assuming $\rho$ has fidelity at least $\tau$ with a stabilizer product state, the algorithm runs in time $n^{O(1 + \log(1/\tau))} / \varepsilon^2$. This runtime is quasipolynomial in all parameters, and polynomial if $\tau$ is a constant.

Related papers

• Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation [16.499689832762765]
  We study the task of tomography: given copies of an unknown $n$-qubit state $rho$ which has fidelity $tau$ with some state in a given class $C$, find a state which has fidelity $ge tau - epsilon$ with $rho$. We give a new framework, stabilizer bootstrapping, for designing computationally efficient protocols for this task, and use this to get new agnostic tomography protocols for the following classes: stabilizer states and discrete product states.
  arXiv  Detail & Related papers  (2024-08-13T15:23:17Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem. We consider detecting the presence of a planted $Gr(ngamma, n-alpha)$ subhypergraph in a $Gr(n, n-beta) hypergraph. Our results are already new in the graph case $r=2$, as we consider the subtle log-density regime where hardness based on average-case reductions is not known.
  arXiv  Detail & Related papers  (2023-04-17T10:38:08Z)
• 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)
• An Optimal Algorithm for Strongly Convex Min-min Optimization [79.11017157526815]
  Existing optimal first-order methods require $mathcalO(sqrtmaxkappa_x,kappa_y log 1/epsilon)$ of computations of both $nabla_x f(x,y)$ and $nabla_y f(x,y)$. We propose a new algorithm that only requires $mathcalO(sqrtkappa_x log 1/epsilon)$ of computations of $nabla_x f(x,
  arXiv  Detail & Related papers  (2022-12-29T19:26:12Z)
• Learning quantum graph states with product measurements [22.463154358632472]
  We consider the problem of learning $N$ identical copies of an unknown $n$-qubit quantum graph state with product measurements. We detail an explicit algorithm that uses product measurements on multiple identical copies of such graph states to learn them.
  arXiv  Detail & Related papers  (2022-05-13T02:55:21Z)
• Quantum algorithm for matrix functions by Cauchy's integral formula [1.399948157377307]
  We consider the problem of obtaining quantum state $lvert f rangle$ corresponding to vector $f(A)boldsymbolb$. We propose a quantum algorithm that uses Cauchy's integral formula and the trapezoidal rule as an approach that avoids eigenvalue estimation.
  arXiv  Detail & Related papers  (2021-06-15T12:10:16Z)
• Lower Bounds on Stabilizer Rank [3.265773263570237]
  We prove that for a sufficiently small constant $delta, the stabilizer rank of any state which is $$-close to those states is $Omega(sqrtn/log n)$. This is the first non-trivial lower bound for approximate stabilizer rank.
  arXiv  Detail & Related papers  (2021-06-06T19:27:51Z)
• Improved quantum data analysis [1.8416014644193066]
  We give a quantum "Threshold Search" algorithm that requires only $O(log2 m)/epsilon2)$ samples of a $d$-dimensional state. We also give an alternative Hypothesis Selection method using $tildeO((log3 m)/epsilon2)$ samples.
  arXiv  Detail & Related papers  (2020-11-22T01:22:37Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  We study the problem of agnostic $Q$-learning with function approximation in deterministic systems. We show that if $delta = Oleft(rho/sqrtdim_Eright)$, then one can find the optimal policy using $Oleft(dim_Eright)$.
  arXiv  Detail & Related papers  (2020-02-17T18:41:49Z)

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.