Quantum Algorithms for Identifying Hidden Strings with Applications to Matroid Problems

• URL: http://arxiv.org/abs/2211.10667v1
• Date: Sat, 19 Nov 2022 11:14:19 GMT
• Title: Quantum Algorithms for Identifying Hidden Strings with Applications to Matroid Problems
• Authors: Xiaowei Huang, Shihao Zhang and Lvzhou Li
• Abstract summary: We present a quantum algorithm consuming $O(1)$ queries to the max inner product oracle for identifying the pair $s, s'$. Also, we present a quantum algorithm consuming $fracn2+O(sqrtn)$ queries to the subset oracle, and prove that any classical algorithm requires at least $n+Omega(1)$ queries.
• Score: 8.347058637480506
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we explore quantum speedups for the problem, inspired by matroid theory, of identifying a pair of $n$-bit binary strings that are promised to have the same number of 1s and differ in exactly two bits, by using the max inner product oracle and the sub-set oracle. More specifically, given two string $s, s'\in\{0, 1\}^n$ satisfying the above constraints, for any $x\in\{0, 1\}^n$ the max inner product oracle $O_{max}(x)$ returns the max value between $s\cdot x$ and $s'\cdot x$, and the sub-set oracle $O_{sub}(x)$ indicates whether the index set of the 1s in $x$ is a subset of that in $s$ or $s'$. We present a quantum algorithm consuming $O(1)$ queries to the max inner product oracle for identifying the pair $\{s, s'\}$, and prove that any classical algorithm requires $\Omega(n/\log_{2}n)$ queries. Also, we present a quantum algorithm consuming $\frac{n}{2}+O(\sqrt{n})$ queries to the subset oracle, and prove that any classical algorithm requires at least $n+\Omega(1)$ queries. Therefore, quantum speedups are revealed in the two oracle models. Furthermore, the above results are applied to the problem in matroid theory of finding all the bases of a 2-bases matroid, where a matroid is called $k$-bases if it has $k$ bases.

Related papers

• Quantum Search with Noisy Oracle [0.0]
  For every oracle call, with probability $p>0$ completely depolarizes the query registers, while otherwise working properly. We show that, for all $ple 0.99$, the quantum noisy-query complexity of the unstructured search is $tildeTheta(maxnp,sqrtn)$. The lower bound $Omega(maxnp,sqrt n)$ holds also for the dephasing noise and even when, for every oracle call, the algorithm is provided with a flag indicating whether the error has occurred.
  arXiv  Detail & Related papers  (2023-09-26T14:00:23Z)
• Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
  We show how to find all $k$ marked elements in a list of size $N$ using the optimal number $O(sqrtN k)$ of quantum queries.
  arXiv  Detail & Related papers  (2023-02-20T19:11:44Z)
• 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)
• Quantum algorithm for learning secret strings and its experimental demonstration [2.924463125497859]
  We consider the secret-string-learning problem in the teacher-student setting. We present an optimal classical deterministic algorithm learning any $s$ using $n$ queries. We obtain a quantum algorithm learning the $n$-bit secret string $s$ with certainty.
  arXiv  Detail & Related papers  (2022-06-22T17:15:45Z)
• The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization [88.91190483500932]
  We study the fundamental open question of finding the optimal high-order algorithm for solving smooth convex minimization problems. The reason for this is that these algorithms require performing a complex binary procedure, which makes them neither optimal nor practical. We fix this fundamental issue by providing the first algorithm with $mathcalOleft(epsilon-2/(p+1)right) $pth order oracle complexity.
  arXiv  Detail & Related papers  (2022-05-19T16:04:40Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• Simplified Quantum Algorithm for the Oracle Identification Problem [0.0]
  oracle access to bits of an unknown string $x$ of length $n$, with the promise that it belongs to a known set $Csubseteq0,1n$. The goal is to identify $x$ using as few queries to the oracle as possible. We develop a quantum query algorithm for this problem with query complexity $Oleft(sqrtfracnlog M log(n/log M)+1right)$, where $M$ is the size of $C$.
  arXiv  Detail & Related papers  (2021-09-08T19:48:27Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• 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)
• Query complexity of heavy hitter estimation [6.373263986460191]
  We consider the problem of identifying the subset $mathcalSgamma_mathcalP$ of elements in the support of an underlying distribution $mathcalP$. We consider two query models: $(a)$ each query is an index $i$ and the oracle return the value $X_i$ and $(b)$ each query is a pair $(i,j)$. For each of these query models, we design sequential estimation algorithms which at each round, either decide what query to send to the oracle depending on the entire
  arXiv  Detail & Related papers  (2020-05-29T07:15:46Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020) The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
  arXiv  Detail & Related papers  (2020-02-17T10:53:50Z)

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.