Learning quantum graph states with product measurements
- URL: http://arxiv.org/abs/2205.06432v1
- Date: Fri, 13 May 2022 02:55:21 GMT
- Title: Learning quantum graph states with product measurements
- Authors: Yingkai Ouyang and Marco Tomamichel
- Abstract summary: 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.
- Score: 22.463154358632472
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of learning $N$ identical copies of an unknown
$n$-qubit quantum graph state with product measurements. These graph states
have corresponding graphs where every vertex has exactly $d$ neighboring
vertices. Here, we detail an explicit algorithm that uses product measurements
on multiple identical copies of such graph states to learn them. When $n \gg d$
and $N = O(d \log(1/\epsilon) + d^2 \log n ),$ this algorithm correctly learns
the graph state with probability at least $1- \epsilon$. From channel coding
theory, we find that for arbitrary joint measurements on graph states, any
learning algorithm achieving this accuracy requires at least $\Omega(\log
(1/\epsilon) + d \log n)$ copies when $d=o(\sqrt n)$. We also supply bounds on
$N$ when every graph state encounters identical and independent depolarizing
errors on each qubit.
Related papers
- Agnostic Tomography of Stabilizer Product States [0.43123403062068827]
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$.
arXiv Detail & Related papers (2024-04-04T21:39:47Z) - Algoritmo de Contagem Qu\^antico Aplicado ao Grafo Bipartido Completo [0.0]
Grover's algorithm is capable of finding $k$ elements in an unordered database with $N$ elements using $O(sqrtN/k)$ steps.
This work tackles the problem of using the quantum counting algorithm for estimating the value $k$ of marked elements in other graphs.
arXiv Detail & Related papers (2023-12-05T21:15:09Z) - 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) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
We show that for datasets with strong inherent anti-correlations, a suitable graph contains both positive and negative edge weights.
We propose a linear-time signed graph sampling method centered on the concept of balanced signed graphs.
Experimental results show that our signed graph sampling method outperformed existing fast sampling schemes noticeably on various datasets.
arXiv Detail & Related papers (2022-08-18T09:19:01Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling.
Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
arXiv Detail & Related papers (2021-10-21T18:43:00Z) - Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
This paper deals with the problem of graph matching or network alignment for ErdHos--R'enyi graphs.
It can be viewed as a noisy average-case version of the graph isomorphism problem.
arXiv Detail & Related papers (2021-10-11T05:07:50Z) - Random Graph Matching with Improved Noise Robustness [2.294014185517203]
We propose a new algorithm for graph matching under probabilistic models.
Our algorithm recovers the underlying matching with high probability when $alpha le 1 / (log log n)C$.
This improves the condition $alpha le 1 / (log n)C$ achieved in previous work.
arXiv Detail & Related papers (2021-01-28T02:39:27Z) - Quantum algorithms for graph problems with cut queries [17.149741568581096]
We show that a quantum algorithm can learn a graph with maximum degree $d$ after $O(d log(n)2)$ many cut queries.
We also show that a quantum algorithm can learn a general graph with $O(sqrtm log(n)3/2)$ many cut queries.
arXiv Detail & Related papers (2020-07-16T12:21:01Z) - 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) - Scalable Deep Generative Modeling for Sparse Graphs [105.60961114312686]
Existing deep neural methods require $Omega(n2)$ complexity by building up the adjacency matrix.
We develop a novel autoregressive model, named BiGG, that utilizes this sparsity to avoid generating the full adjacency matrix.
During training this autoregressive model can be parallelized with $O(log n)$ synchronization stages.
arXiv Detail & Related papers (2020-06-28T04:37:57Z) - 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)
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.