Quantum exact search with adjustable parameters and its applications

• URL: http://arxiv.org/abs/2210.12644v1
• Date: Sun, 23 Oct 2022 07:53:57 GMT
• Title: Quantum exact search with adjustable parameters and its applications
• Authors: Guanzhong Li and Lvzhou Li
• Abstract summary: Grover's algorithm provides a quadratic speedup over classical algorithms to search for marked elements in an unstructured database. We present a search framework with adjustable parameters that can be geometrically seen as rotating about a fixed axis on the Bloch sphere.
• Score: 0.2741266294612775
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Grover's algorithm provides a quadratic speedup over classical algorithms to search for marked elements in an unstructured database. When it is known beforehand there are $M$ marked elements in $N$ elements, there exist several schemes to achieve the exact version that returns a marked element with certainty, by using the generalized Grover's iteration $G(\alpha,\beta):=S_r(\beta)\, S_o(\alpha)$, where the phase oracle $S_o(\alpha)$ multiplies a marked state by $e^{i\alpha}$, and the phase rotation $S_r(\beta)$ multiplies the initial state $\ket{\psi_0}$ (an equal-superposition of all states) by $e^{-i\beta}$. However, in all the existing schemes the value range of $\alpha$ and $\beta$ is limited; for instance, in the three early schemes $\alpha$ and $\beta$ are determined by $M/N$. Thus, a natural question arises: {\it Given the phase oracle $S_o(\alpha)$ with an arbitrary angle $\alpha$, or the phase rotation $S_r(\beta)$ with an arbitrary angle $\beta$, can we always construct an exact search algorithm without sacrificing the quadratic speedup advantage?} The significance of this problem lies not only in the expansion of mathematical form, but also in its application value. We answer the question affirmatively, by presenting a search framework with adjustable parameters. Technically, we propose the {\it fixed-axis-rotation (FXR) method} where each iteration of the search algorithm can be geometrically seen as rotating about a fixed axis on the Bloch sphere. Furthermore, two applications of the proposed search framework are developed: the first is to learn exactly the secret string hidden by the Hamming distance oracle, and the other to solve the element distinctness promise problem deterministically. The two applications correspond to the two different cases where $\alpha$ or $\beta$ is fixed respectively.

Related papers

• One-Query Quantum Algorithms for the Index-$q$ Hidden Subgroup Problem [1.4146420810689422]
  The Bernstein-Vazirani problem is an instance of the hidden subgroup problem (HSP)<n>We present the index-$q$ HSP: determine whether a hidden subgroup $H le G$ has index $1$ or $q$, and, when possible, identify $H$.
  arXiv  Detail & Related papers  (2025-10-12T10:42:50Z)
• Actively Learning Halfspaces without Synthetic Data [34.777547976926456]
  We design efficient algorithms for learning halfspaces without point synthesis.<n>As a corollary, we obtain an optimal $O(d + log n)$ query deterministic learner for axis-aligned halfspaces.<n>Our algorithm solves the more general problem of learning a Boolean function $f$ over $n$ elements which is monotone under at least one of $D$ provided orderings.
  arXiv  Detail & Related papers  (2025-09-25T07:39:25Z)
• Quantum Search on Computation Trees [0.0]
  We show a generalization of the quantum walk algorithm for search in backtracking trees by Montanaro (ToC)<n>This framework provides an easy and convenient way to re-obtain a number of other quantum frameworks like variable time search, quantum divide & conquer and bomb query algorithms.
  arXiv  Detail & Related papers  (2025-05-28T14:35:18Z)
• Quantum linear system algorithm with optimal queries to initial state preparation [0.0]
  Quantum algorithms for linear systems produce the solution state $A-1|brangle$ by querying two oracles. We present a quantum linear system algorithm making $mathbfThetaleft (1/sqrtpright)$ queries to $O_b$, which is optimal in the success probability. In various applications such as solving differential equations, we can further improve the dependence on $p$ using a block preconditioning scheme.
  arXiv  Detail & Related papers  (2024-10-23T18:00:01Z)
• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  We show that for any $K$, there is a universal set" $U subset [n]$ of size independent of $n$, such that for any $Q$ and any row $i$, the large attention scores $A_i,j$ in row $i$ of $A$ all have $jin U$. We empirically show the benefits of our scheme for vision transformers, showing how to train new models that use our universal set while training as well.
  arXiv  Detail & Related papers  (2024-10-07T19:47:13Z)
• Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
  We show that our algorithm has an $tilde O(n2)$ when $k=O(n0.729)$. In particular, our algorithm has an $tilde O(n2)$ when $k=O(n0.729)$. Our main algorithm can be viewed as a randomized block coordinate descent method.
  arXiv  Detail & Related papers  (2023-12-14T12:53:34Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2022-04-13T22:18:47Z)
• 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)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  We study the problem of list-decodable mean estimation, where an adversary can corrupt a majority of the dataset. We develop new algorithms for list-decodable mean estimation, achieving nearly-optimal statistical guarantees.
  arXiv  Detail & Related papers  (2021-06-16T03:34:14Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  We consider the problem of learning a latent $k$-vertex simplex $KsubsetmathbbRdtimes n$, given access to $AinmathbbRdtimes n$. We show that the dependence on $k$ in the running time is unnecessary given a natural assumption about the mass of the top $k$ singular values of $A$.
  arXiv  Detail & Related papers  (2021-05-17T16:40:48Z)
• An extension of the angular synchronization problem to the heterogeneous setting [8.391320712953553]
  We find a generalization to the setting where there exist $k$ unknown groups of angles $theta_l,1, dots,theta_l,n$, for $l=1,dots,k$. This problem arises in a variety of applications, including computer vision, time synchronization of distributed networks, and ranking from preference relationships.
  arXiv  Detail & Related papers  (2020-12-29T20:29:10Z)
• 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)
• 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)
• Problem-Complexity Adaptive Model Selection for Stochastic Linear Bandits [20.207989166682832]
  We consider the problem of model selection for two popular linear bandit settings. In the first setting, we consider the $K$ armed mixture bandits, where the mean reward of arm $i in [K]$ is $mu_i+ langle alpha_i,t,theta*|$. We show that ALB achieves regret scaling of $O(|theta*|sqrtT)$, where $|theta*|$ is apriori unknown
  arXiv  Detail & Related papers  (2020-06-04T02:19:00Z)
• Fast digital methods for adiabatic state preparation [0.0]
  We present a quantum algorithm for adiabatic state preparation on a gate-based quantum computer, with complexity polylogarithmic in the inverse error.
  arXiv  Detail & Related papers  (2020-04-08T18:00:01Z)
• 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)
• 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.