Introducing Structure to Expedite Quantum Search

• URL: http://arxiv.org/abs/2006.05828v3
• Date: Tue, 11 May 2021 21:44:21 GMT
• Title: Introducing Structure to Expedite Quantum Search
• Authors: Marcin Bria\'nski, Jan Gwinner, Vladyslav Hlembotskyi, Witold Jarnicki, Szymon Pli\'s, Adam Szady
• Abstract summary: We present a novel quantum algorithm for solving the unstructured search problem with one marked element. Our algorithm is optimal in the total number of elementary gates up to a multiplicative constant. We show how toally reduce the number of elementary gates required to solve the unstructured search problem with multiple marked elements.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a novel quantum algorithm for solving the unstructured search problem with one marked element. Our algorithm allows generating quantum circuits that use asymptotically fewer additional quantum gates than the famous Grover's algorithm and may be successfully executed on NISQ devices. We prove that our algorithm is optimal in the total number of elementary gates up to a multiplicative constant. As many NP-hard problems are not in fact unstructured, we also describe the \emph{partial uncompute} technique which exploits the oracle structure and allows a significant reduction in the number of elementary gates required to find the solution. Combining these results allows us to use asymptotically smaller number of elementary gates than the Grover's algorithm in various applications, keeping the number of queries to the oracle essentially the same. We show how the results can be applied to solve hard combinatorial problems, for example Unique k-SAT. Additionally, we show how to asymptotically reduce the number of elementary gates required to solve the unstructured search problem with multiple marked elements.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Discretized Quantum Exhaustive Search for Variational Quantum Algorithms [0.0]
  Currently available quantum devices have only a limited amount of qubits and a high level of noise, limiting the size of problems that can be solved accurately with those devices. We propose a novel method that can improve variational quantum algorithms -- discretized quantum exhaustive search''
  arXiv  Detail & Related papers  (2024-07-24T22:06:05Z)
• Efficient Implementation of a Quantum Search Algorithm for Arbitrary N [0.0]
  This paper presents an enhancement to Grover's search algorithm for instances where $N$ is not a power of 2. By employing an efficient algorithm for the preparation of uniform quantum superposition states over a subset of the computational basis states, we demonstrate that a considerable reduction in the number of oracle calls (and Grover's iterations) can be achieved in many cases.
  arXiv  Detail & Related papers  (2024-06-19T19:16:40Z)
• One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
  We show that quantum Las Vegas query complexity is exactly equal to the quantum adversary bound. This is achieved by transforming a feasible solution to the adversary inversion problem into a quantum query algorithm.
  arXiv  Detail & Related papers  (2023-01-05T11:05:22Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  Coherent control of quantum computations can be used to improve some quantum protocols and algorithms. We refine the PBS-calculus, a graphical language for coherent control inspired by quantum optics.
  arXiv  Detail & Related papers  (2022-02-10T18:59:52Z)
• Hardware Efficient Quantum Search Algorithm [17.74233101199813]
  We propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. The circuit cost reduction leads to a remarkable improvement in the system success rates.
  arXiv  Detail & Related papers  (2021-03-26T01:08:50Z)
• Number Partitioning with Grover's Algorithm in Central Spin Systems [0.0]
  We propose a Grover search for solutions to a class of NP-complete decision problems known as subset sum problems. Each problem instance is encoded in the couplings of a set of qubits to a central spin or boson, which enables a realization of the oracle without knowledge of the solution.
  arXiv  Detail & Related papers  (2020-09-11T17:31:39Z)
• Topological Quantum Compiling with Reinforcement Learning [7.741584909637626]
  We introduce an efficient algorithm that compiles an arbitrary single-qubit gate into a sequence of elementary gates from a finite universal set. Our algorithm may carry over to other challenging quantum discrete problems, thus opening up a new avenue for intriguing applications of deep learning in quantum physics.
  arXiv  Detail & Related papers  (2020-04-09T18:00:01Z)

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.