Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem

• URL: http://arxiv.org/abs/2404.19476v1
• Date: Tue, 30 Apr 2024 11:45:49 GMT
• Title: Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem
• Authors: Aleksandrs Belovs,
• Abstract summary: In this paper, we give a short proof of the optimal linear hitting time for a welded tree problem by a discrete-time quantum walk. The same technique can be applied to other 1-dimensional hierarchical graphs.
• Score: 55.80819771134007
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Up to now, relatively few exponential quantum speed-ups have been achieved. Out of them, the welded tree problem (Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman'2003) is one of the unusual examples, as the exponential speed-up is attained by a quantum walk. In this paper, we give a very short proof of the optimal linear hitting time for this problem by a discrete-time quantum walk, which is based on a simple modification of the electric quantum walk framework. The same technique can be applied to other 1-dimensional hierarchical graphs, yielding results similar to (Balasubramanian, Li, and Harrow'2023).

Related papers

• Towards Entropic Constraints on Quantum Speedups [0.0]
  Some quantum algorithms have "quantum speedups": improved time complexity as compared with the best-known classical algorithms for solving the same tasks. Can we understand what fuels these speedups from an entropic perspective? Information theory gives us a multitude of metrics we might choose from to measure how fundamentally 'quantum' is the behavior of a quantum computer running an algorithm.
  arXiv  Detail & Related papers  (2024-11-05T19:00:04Z)
• Quantum walks, the discrete wave equation and Chebyshev polynomials [1.0878040851638]
  A quantum walk is the quantum analogue of a random walk. We show that quantum walks can speed up the spreading or mixing rate of random walks on graphs.
  arXiv  Detail & Related papers  (2024-02-12T17:15:19Z)
• Recovering the original simplicity: succinct and deterministic quantum algorithm for the welded tree problem [0.0]
  This work revisits quantum algorithms for the well-known welded tree problem. It proposes a very succinct quantum algorithm based on the simplest coined quantum walks.
  arXiv  Detail & Related papers  (2023-04-17T16:03:50Z)
• 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)
• Quantum communication complexity of linear regression [0.05076419064097732]
  We show that quantum computers have provable and exponential speedups in terms of communication for some fundamental linear algebra problems. We propose an efficient quantum protocol for quantum singular value transformation.
  arXiv  Detail & Related papers  (2022-10-04T13:27:01Z)
• A shortcut to adiabaticity in a cavity with a moving mirror [58.720142291102135]
  We describe for the first time how to implement shortcuts to adiabaticity in quantum field theory. The shortcuts take place whenever there is no dynamical Casimir effect. We obtain a fundamental limit for the efficiency of an Otto cycle with the quantum field as a working system.
  arXiv  Detail & Related papers  (2022-02-01T20:40:57Z)
• 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)
• Improved Upper Bounds for the Hitting Times of Quantum Walks [0.0]
  Continuous-time quantum walks have proven to be an extremely useful framework for the design of quantum algorithms. We provide improved upper bounds for the quantum hitting time that can be applied to several CTQW-based quantum algorithms.
  arXiv  Detail & Related papers  (2020-05-08T14:25:24Z)
• Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
  Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling. We examine the constraints of the observed quantum runtime advantage in a larger number of qubits and gates.
  arXiv  Detail & Related papers  (2020-05-05T20:11:53Z)

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.