Optimal exact quantum algorithm for the promised element distinctness problem

• URL: http://arxiv.org/abs/2211.05443v1
• Date: Thu, 10 Nov 2022 09:33:13 GMT
• Title: Optimal exact quantum algorithm for the promised element distinctness problem
• Authors: Guanzhong Li and Lvzhou Li
• Abstract summary: An element distinctness problem is to determine whether a string $x=(x_1,ldots,x_N)$ of $N$ elements contains two elements of the same value. We propose an exact quantum algorithm for the promise problem which never errs and requires $O(N2/3)$ queries.
• Score: 0.2741266294612775
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The element distinctness problem is to determine whether a string $x=(x_1,\ldots,x_N)$ of $N$ elements contains two elements of the same value (a.k.a colliding pair), for which Ambainis proposed an optimal quantum algorithm. The idea behind Ambainis' algorithm is to first reduce the problem to the promised version in which $x$ is promised to contain at most one colliding pair, and then design an algorithm $\mathcal{A}$ requiring $O(N^{2/3})$ queries based on quantum walk search for the promise problem. However, $\mathcal{A}$ is probabilistic and may fail to give the right answer. We thus, in this work, design an exact quantum algorithm for the promise problem which never errs and requires $O(N^{2/3})$ queries. This algorithm is proved optimal. Technically, we modify the quantum walk search operator on quasi-Johnson graph to have arbitrary phases, and then use Jordan's lemma as the analyzing tool to reduce the quantum walk search operator to the generalized Grover's operator. This allows us to utilize the recently proposed fixed-axis-rotation (FXR) method for exact quantum search, and hence achieve 100\% success.

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)
• 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)
• On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
  We present an exact quantum algorithm for computing $textMOD_mn$. We show exact quantum query complexity of a broad class of symmetric functions that map $0,1n$ to a finite set $X$ is less than $n$.
  arXiv  Detail & Related papers  (2023-03-20T08:17:32Z)
• Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
  We show that randomization is necessary to obtain a dimension-free dimension-free algorithm. Our algorithm yields the first deterministic dimension-free algorithm for optimizing ReLU networks.
  arXiv  Detail & Related papers  (2023-02-16T13:57:19Z)
• 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)
• Efficient quantum algorithms for solving quantum linear system problems [0.0]
  We present two quantum algorithms for solving the problem of finding the right singular vector with singular value zero of an augmented matrix $C$. Both algorithms meet the optimal query complexity in $kappa $, and are simpler than previous algorithms.
  arXiv  Detail & Related papers  (2022-08-14T02:49:26Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Finding many Collisions via Reusable Quantum Walks [1.376408511310322]
  Collision finding is an ubiquitous problem in cryptanalysis. In this paper, we improve the algorithms for this problem and, in particular, extend the range of admissible parameters. As an application, we improve the quantum sieving algorithms for the shortest vector problem.
  arXiv  Detail & Related papers  (2022-05-27T14:50:45Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• 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)

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.