Quantum algorithms and the power of forgetting
- URL: http://arxiv.org/abs/2211.12447v1
- Date: Tue, 22 Nov 2022 18:04:10 GMT
- Title: Quantum algorithms and the power of forgetting
- Authors: Andrew M. Childs, Matthew Coudron, Amin Shiraz Gilani
- Abstract summary: We show that a natural class of efficient quantum algorithms provably cannot find a path from ENTRANCE to EXIT.
While this does not rule out the possibility of a quantum algorithm that efficiently finds a path, it is unclear how an algorithm could benefit from this behavior.
- Score: 1.5791732557395555
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The so-called welded tree problem provides an example of a black-box problem
that can be solved exponentially faster by a quantum walk than by any classical
algorithm. Given the name of a special ENTRANCE vertex, a quantum walk can find
another distinguished EXIT vertex using polynomially many queries, though
without finding any particular path from ENTRANCE to EXIT. It has been an open
problem for twenty years whether there is an efficient quantum algorithm for
finding such a path, or if the path-finding problem is hard even for quantum
computers. We show that a natural class of efficient quantum algorithms
provably cannot find a path from ENTRANCE to EXIT. Specifically, we consider
algorithms that, within each branch of their superposition, always store a set
of vertex labels that form a connected subgraph including the ENTRANCE, and
that only provide these vertex labels as inputs to the oracle. While this does
not rule out the possibility of a quantum algorithm that efficiently finds a
path, it is unclear how an algorithm could benefit by deviating from this
behavior. Our no-go result suggests that, for some problems, quantum algorithms
must necessarily forget the path they take to reach a solution in order to
outperform classical computation.
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) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry.
The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time.
Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
arXiv Detail & Related papers (2024-05-02T10:29:06Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al.
We apply our algorithm to the quantum information bottleneck with three quantum systems.
Our numerical analysis shows that our algorithm is better than their algorithm.
arXiv Detail & Related papers (2023-11-19T00:06:11Z) - Exponential speedup of quantum algorithms for the pathfinding problem [5.260626311429307]
Given $s, t$ in an unweighted undirected graph $G$, the goal of the pathfinding problem is to find an $s$-$t$ path.
We construct a graph $G$ based on welded trees and define a pathfinding problem in the adjacency list oracle $O$.
We prove that no classical algorithm can find an $s$-$t$ path in subexponential time with high probability.
arXiv Detail & Related papers (2023-07-24T02:50:34Z) - Making the cut: two methods for breaking down a quantum algorithm [0.0]
It remains a major challenge to find quantum algorithms that may reach computational advantage in the present era of noisy, small-scale quantum hardware.
We identify and characterize two methods of breaking down'' quantum algorithms into rounds of lower (query) depth.
We show that for the first problem parallelization offers the best performance, while for the second is the better choice.
arXiv Detail & Related papers (2023-05-17T18:00:06Z) - 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) - 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) - Robust Quantum Walk Search Without Knowing the Number of Marked Vertices [0.2320417845168326]
Existing quantum walk-based search algorithms suffer from the souffl'e problem.
We present a new quantum walk-based search framework that achieves robustness without sacrificing the quantum speedup.
arXiv Detail & Related papers (2021-11-17T10:04:44Z) - 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)
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.