Quantum Counting on the Complete Bipartite Graph
- URL: http://arxiv.org/abs/2311.10407v2
- Date: Fri, 8 Dec 2023 14:10:38 GMT
- Title: Quantum Counting on the Complete Bipartite Graph
- Authors: Gustavo A. Bezerra, Raqueline A. M. Santos, and Renato Portugal
- Abstract summary: Quantum counting is a key quantum algorithm that aims to determine the number of marked elements in a database.
Since Grover's algorithm can be viewed as a quantum walk on a complete graph, a natural way to extend quantum counting is to use the evolution operator of quantum-walk-based search on non-complete graphs.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum counting is a key quantum algorithm that aims to determine the number
of marked elements in a database. This algorithm is based on the quantum phase
estimation algorithm and uses the evolution operator of Grover's algorithm
because its non-trivial eigenvalues are dependent on the number of marked
elements. Since Grover's algorithm can be viewed as a quantum walk on a
complete graph, a natural way to extend quantum counting is to use the
evolution operator of quantum-walk-based search on non-complete graphs instead
of Grover's operator. In this paper, we explore this extension by analyzing the
coined quantum walk on the complete bipartite graph with an arbitrary number of
marked vertices. We show that some eigenvalues of the evolution operator depend
on the number of marked vertices and using this fact we show that the quantum
phase estimation can be used to obtain the number of marked vertices. The time
complexity for estimating the number of marked vertices in the bipartite graph
with our algorithm aligns closely with that of the original quantum counting
algorithm.
Related papers
- Quantum Walk Search on Complete Multipartite Graph with Multiple Marked Vertices [7.922488341886121]
This paper examines the quantum walk search algorithm on complete multipartite graphs.
We employ the coined quantum walk model and achieve quadratic speedup.
We also provide the numerical simulation and circuit implementation of our quantum algorithm.
arXiv Detail & Related papers (2024-10-07T11:13:41Z) - Deterministic Search on Complete Bipartite Graphs by Continuous Time Quantum Walk [0.8057006406834466]
This paper presents a deterministic search algorithm on complete bipartite graphs.
We address the most general case of multiple marked states, so there is a problem of estimating the number of marked states.
We construct a quantum counting algorithm based on the spectrum structure of the search operator.
arXiv Detail & Related papers (2024-04-02T05:09:33Z) - 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) - A high-fidelity quantum state transfer algorithm on the complete
bipartite graph [15.305667582809924]
Current quantum state transfer algorithms on the complete bipartite graph suffer from low fidelity in some cases.
We propose a two-stage quantum state transfer algorithm on the complete bipartite graph.
arXiv Detail & Related papers (2023-02-23T11:20:12Z) - Compilation of algorithm-specific graph states for quantum circuits [55.90903601048249]
We present a quantum circuit compiler that prepares an algorithm-specific graph state from quantum circuits described in high level languages.
The computation can then be implemented using a series of non-Pauli measurements on this graph state.
arXiv Detail & Related papers (2022-09-15T14:52:31Z) - 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) - From Quantum Graph Computing to Quantum Graph Learning: A Survey [86.8206129053725]
We first elaborate the correlations between quantum mechanics and graph theory to show that quantum computers are able to generate useful solutions.
For its practicability and wide-applicability, we give a brief review of typical graph learning techniques.
We give a snapshot of quantum graph learning where expectations serve as a catalyst for subsequent research.
arXiv Detail & Related papers (2022-02-19T02:56:47Z) - Benchmarking Small-Scale Quantum Devices on Computing Graph Edit
Distance [52.77024349608834]
Graph Edit Distance (GED) measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical.
In this paper we present a comparative study of two quantum approaches to computing GED.
arXiv Detail & Related papers (2021-11-19T12:35:26Z) - 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) - Quantum walk-based search algorithms with multiple marked vertices [0.0]
The quantum walk is a powerful tool to develop quantum algorithms.
We extend previous analytical methods based on Szegedy's quantum walk.
Two examples based on the coined quantum walk on two-dimensional lattices and hypercubes show the details of our method.
arXiv Detail & Related papers (2021-03-23T22:57:07Z)
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.