Derandomization of quantum algorithm for triangle finding
- URL: http://arxiv.org/abs/2309.13268v1
- Date: Sat, 23 Sep 2023 05:24:59 GMT
- Title: Derandomization of quantum algorithm for triangle finding
- Authors: Guanzhong Li, Lvzhou Li
- Abstract summary: Derandomization is the process of taking a randomized algorithm and turning it into a deterministic algorithm.
In quantum computing, it is challenging and intriguing to derandomize quantum algorithms, due to the inherent randomness of quantum mechanics.
We show that when the graph is promised to contain at most one target triangle, there exists a deterministic quantum algorithm that either finds the triangle if it exists or outputs no triangle'' if none exists.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Derandomization is the process of taking a randomized algorithm and turning
it into a deterministic algorithm, which has attracted great attention in
classical computing. In quantum computing, it is challenging and intriguing to
derandomize quantum algorithms, due to the inherent randomness of quantum
mechanics. The significance of derandomizing quantum algorithms lies not only
in theoretically proving that the success probability can essentially be 1
without sacrificing quantum speedups, but also in experimentally improving the
success rate when the algorithm is implemented on a real quantum computer.
In this paper, we focus on derandomizing quanmtum algorithms for the triangle
sum problem (including the famous triangle finding problem as a special case),
which asks to find a triangle in an edge-weighted graph with $n$ vertices, such
that its edges sum up to a given weight.We show that when the graph is promised
to contain at most one target triangle, there exists a deterministic quantum
algorithm that either finds the triangle if it exists or outputs ``no
triangle'' if none exists. It makes $O(n^{9/7})$ queries to the edge weight
matrix oracle, and thus has the same complexity with the state-of-art
bounded-error quantum algorithm. To achieve this derandomization, we make full
use several techniques:nested quantum walks with quantum data structure,
deterministic quantum search with adjustable parameters, and dimensional
reduction of quantum walk search on Johnson graph.
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) - How to Design a Quantum Streaming Algorithm Without Knowing Anything About Quantum Computing [0.2184775414778289]
We show that advantages in space complexity are possible for quantum algorithms over their classical counterparts in the streaming model.
We give a simple quantum sketch that encompasses all these results, allowing them to be derived from entirely classical algorithms using our quantum sketch as a black box.
arXiv Detail & Related papers (2024-10-24T17:11:37Z) - 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) - 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) - Simulating the quantum Fourier transform, Grover's algorithm, and the quantum counting algorithm with limited entanglement using tensor-networks [0.0]
We simulate the execution of quantum algorithms with limited entanglement.
We find that the algorithms can be executed with high fidelity even if the entanglement is somewhat reduced.
Our results are promising for the execution of these algorithms on future quantum computers.
arXiv Detail & Related papers (2023-04-04T12:42:18Z) - Sample-size-reduction of quantum states for the noisy linear problem [0.0]
We show that it is possible to reduce a quantum sample size in a quantum random access memory (QRAM) to the linearithmic order.
We achieve a shorter run-time for the noisy linear problem.
arXiv Detail & Related papers (2023-01-08T05:53:17Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
We design, implement, and evaluate three hybrid quantum k-Means algorithms.
We exploit quantum phenomena to speed up the computation of distances.
We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
arXiv Detail & Related papers (2022-12-13T16:04:16Z) - 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) - 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) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard.
We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware.
The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
arXiv Detail & Related papers (2021-07-08T17:59:55Z) - 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.