Quantum Search with In-Place Queries

• URL: http://arxiv.org/abs/2504.03620v1
• Date: Fri, 04 Apr 2025 17:37:42 GMT
• Title: Quantum Search with In-Place Queries
• Authors: Blake Holman, Ronak Ramachandran, Justin Yirka,
• Abstract summary: We design a quantum algorithm for Permutation Inversion using $O(sqrtN)$ in-place queries.<n>We show that there are indeed problems which require fewer XOR queries than in-place queries.
• Score: 1.1999555634662633
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum query complexity is typically characterized in terms of XOR queries |x,y> to |x,y+f(x)> or phase queries, which ensure that even queries to non-invertible functions are unitary. When querying a permutation, another natural model is unitary: in-place queries |x> to |f(x)>. Some problems are known to require exponentially fewer in-place queries than XOR queries, but no separation has been shown in the opposite direction. A candidate for such a separation was the problem of inverting a permutation over N elements. This task, equivalent to unstructured search in the context of permutations, is solvable with $O(\sqrt{N})$ XOR queries but was conjectured to require $\Omega(N)$ in-place queries. We refute this conjecture by designing a quantum algorithm for Permutation Inversion using $O(\sqrt{N})$ in-place queries. Our algorithm achieves the same speedup as Grover's algorithm despite the inability to efficiently uncompute queries or perform straightforward oracle-controlled reflections. Nonetheless, we show that there are indeed problems which require fewer XOR queries than in-place queries. We introduce a subspace-conversion problem called Function Erasure that requires 1 XOR query and $\Theta(\sqrt{N})$ in-place queries. Then, we build on a recent extension of the quantum adversary method to characterize exact conditions for a decision problem to exhibit such a separation, and we propose a candidate problem.

Related papers

• Clustering with Non-adaptive Subset Queries [16.662507957069813]
  Given a query $S subset U$, $|S|=2$, the oracle returns yes if the points are in the same cluster and no otherwise. For adaptive algorithms with pair-wise queries, the number of required queries is known to be $Theta(nk)$. Non-adaptive schemes require $Omega(n2)$ queries, which matches the trivial $O(n2)$ upper bound attained by querying every pair of points.
  arXiv  Detail & Related papers  (2024-09-17T05:56:07Z)
• Quantum Query-Space Lower Bounds Using Branching Programs [0.18416014644193066]
  We show the first explicit query-space lower bound for our restricted version of GQBP. We then generalize the problem to show that the same bound holds for deciding between two strings with a constant Hamming distance. Our results produce an alternative proof of the $Omega(sqrtn)$-lower bound on the query complexity of any non-constant symmetric Boolean function.
  arXiv  Detail & Related papers  (2024-07-09T13:58:53Z)
• Accelerated quantum search using partial oracles and Grover's algorithm [0.0]
  Grover's algorithm, orginally conceived as a means of searching an unordered database, can also be used to extract solutions from the result sets generated by quantum computations. We explore the idea of associating a separate oracle with each bit of the matching condition, obtaining multiple partial oracle functions which can be tested independently. The algorithm is validated against the simplest kind of search scenario, where the incoming index bits are scrambled using a permutation operation.
  arXiv  Detail & Related papers  (2024-03-19T11:32:02Z)
• On the Two-sided Permutation Inversion Problem [45.69327512339002]
  We study the setting in which the oracle allows for quantum queries to both the forward and inverse direction of the permutation. We prove several theorems connecting the hardness of the resulting variations of the inversion problem. Our results indicate that, perhaps surprisingly, the inversion problem does not become significantly easier when the adversary is granted oracle access to the inverse.
  arXiv  Detail & Related papers  (2023-06-23T18:31:48Z)
• Private Query Release via the Johnson-Lindenstrauss Transform [93.20051580730234]
  We introduce a new method for releasing answers to statistical queries with differential privacy. The key idea is to randomly project the query answers to a lower dimensional space. We answer the projected queries using a simple noise-adding mechanism, and lift the answers up to the original dimension.
  arXiv  Detail & Related papers  (2022-08-15T19:19:16Z)
• Variational learning algorithms for quantum query complexity [3.980076328494117]
  We develop variational learning algorithms to study quantum query complexity. We apply our method to analyze various cases of quantum query complexity. Our method can be readily implemented on the near-term Noisy Intermediate-Scale Quantum (NISQ) devices.
  arXiv  Detail & Related papers  (2022-05-16T05:16:15Z)
• Query2Particles: Knowledge Graph Reasoning with Particle Embeddings [49.64006979045662]
  We propose a query embedding method to answer complex logical queries on knowledge graphs with missing edges. The answer entities are selected according to the similarities between the entity embeddings and the query embedding. A complex KG query answering method, Q2P, is proposed to retrieve diverse answers from different areas over the embedding space.
  arXiv  Detail & Related papers  (2022-04-27T11:16:08Z)
• Quantum search-to-decision reductions and the state synthesis problem [0.4248594146171025]
  We show that a quantum algorithm makes queries to a classical decision oracle to output a desired quantum state. We also show that there exists a quantum-time algorithm that can generate a witness for a $mathsfQMA$ problem up to inverse precision. We also explore the more general $textitstate synthesis problem$, in which the goal is to efficiently synthesize a target state.
  arXiv  Detail & Related papers  (2021-11-04T16:52:58Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  The fuzzy or soft objective is a popular generalization of the well-known $k$-means problem. We show that by making few queries, the problem becomes easier to solve.
  arXiv  Detail & Related papers  (2021-06-04T02:32:26Z)
• 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)
• The Sparse Vector Technique, Revisited [67.57692396665915]
  We revisit one of the most basic and widely applicable techniques in the literature of differential privacy. This simple algorithm privately tests whether the value of a given query on a database is close to what we expect it to be. We suggest an alternative, equally simple, algorithm that can continue testing queries as long as any single individual does not contribute to the answer of too many queries.
  arXiv  Detail & Related papers  (2020-10-02T10:50:52Z)
• Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings [84.0206612938464]
  query2box is an embedding-based framework for reasoning over arbitrary queries on incomplete knowledge graphs. We show that query2box is capable of handling arbitrary logical queries with $wedge$, $vee$, $exists$ in a scalable manner. We demonstrate the effectiveness of query2box on three large KGs and show that query2box achieves up to 25% relative improvement over the state of the art.
  arXiv  Detail & Related papers  (2020-02-14T11:20:10Z)

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.