Algoritmo de Contagem Qu\^antico Aplicado ao Grafo Bipartido Completo

• URL: http://arxiv.org/abs/2312.03768v1
• Date: Tue, 5 Dec 2023 21:15:09 GMT
• Title: Algoritmo de Contagem Qu\^antico Aplicado ao Grafo Bipartido Completo
• Authors: Gustavo Alves Bezerra
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Studies on Quantum Computing have been developed since the 1980s, motivating researches on quantum algorithms better than any classical algorithm possible. An example of such algorithms is Grover's algorithm, capable of finding $k$ (marked) elements in an unordered database with $N$ elements using $O(\sqrt{N/k})$ steps. Grover's algorithm can be interpreted as a quantum walk in a complete graph (with loops) containing $N$ vertices from which $k$ are marked. This interpretation motivated search algorithms in other graphs -- complete bipartite graph, grid, and hypercube. Using Grover's algorithm's linear operator, the quantum counting algorithm estimates the value of $k$ with an error of $O(\sqrt{k})$ using $O(\sqrt{N})$ steps. This work tackles the problem of using the quantum counting algorithm for estimating the value $k$ of marked elements in other graphs; more specifically, the complete bipartite graph. It is concluded that for a particular case, running the proposed algorithm at most $t$ times wields an estimation of $k$ with an error of $O(\sqrt{k})$ using $O(t\sqrt{N})$ steps and success probability of at least $(1 - 2^{-t})8/\pi^2$.

Related papers

• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$. We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
  arXiv  Detail & Related papers  (2024-02-09T19:01:48Z)
• Do you know what q-means? [50.045011844765185]
  Clustering is one of the most important tools for analysis of large datasets. We present an improved version of the "$q$-means" algorithm for clustering. We also present a "dequantized" algorithm for $varepsilon which runs in $Obig(frack2varepsilon2(sqrtkd + log(Nd))big.
  arXiv  Detail & Related papers  (2023-08-18T17:52:12Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  We show that an algorithm can obtain $O(log T)$ regret with just $O(sqrtT)$ hints under a natural query model. We also show that $o(sqrtT)$ hints cannot guarantee better than $Omega(sqrtT)$ regret.
  arXiv  Detail & Related papers  (2021-11-09T16:50:18Z)
• Classical algorithms and quantum limitations for maximum cut on high-girth graphs [6.262125516926276]
  We show that every (quantum or classical) one-local algorithm achieves on $D$-regular graphs of $> 5$ a maximum cut of at most $1/2 + C/sqrtD$ for $C=1/sqrt2 approx 0.7071$. We show that there is a classical $k$-local algorithm that achieves a value of $1/2 + C/sqrtD - O (1/sqrtk)$ for $D$-regular graphs of $> 2k+1$, where
  arXiv  Detail & Related papers  (2021-06-10T16:28:23Z)
• Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
  We show that a quantum algorithm can be implemented in time $tilde O(sqrtGT)$. Our algorithm is based on non-binary span programs and their efficient implementation.
  arXiv  Detail & Related papers  (2021-05-18T06:51:11Z)
• Leveraging Unknown Structure in Quantum Query Algorithms [0.0]
  We show a modified span program algorithm to show these speed-ups persist even without having a promise ahead of time. Our algorithm uses $tildeO(sqrtkn)$ queries to solve this problem if there is a path with at most $k$ edges.
  arXiv  Detail & Related papers  (2020-12-02T15:32:52Z)
• 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)
• Resonant Quantum Search with Monitor Qubits [0.0]
  We present an algorithm for the generalized search problem (searching $k$ marked items among $N$ items) based on a continuous Hamiltonian and exploiting resonance. This resonant algorithm has the same time complexity $O(sqrtN/k)$ as the Grover algorithm.
  arXiv  Detail & Related papers  (2020-02-21T19:31:34Z)

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.