Deterministic Search on Complete Bipartite Graphs by Continuous Time Quantum Walk
- URL: http://arxiv.org/abs/2404.01640v2
- Date: Fri, 10 May 2024 10:08:02 GMT
- Title: Deterministic Search on Complete Bipartite Graphs by Continuous Time Quantum Walk
- Authors: Honghong Lin, Yun Shang,
- Abstract summary: 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.
- Score: 0.8057006406834466
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper presents a deterministic search algorithm on complete bipartite graphs. Our algorithm adopts the simple form of alternating iterations of an oracle and a continuous-time quantum walk operator, which is a generalization of Grover's search algorithm. We address the most general case of multiple marked states, so there is a problem of estimating the number of marked states. To this end, we construct a quantum counting algorithm based on the spectrum structure of the search operator. To implement the continuous-time quantum walk operator, we perform Hamiltonian simulation in the quantum circuit model. We achieve simulation in constant time, that is, the complexity of the quantum circuit does not scale with the evolution time.
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 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) - Quantum Counting on the Complete Bipartite Graph [0.0]
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.
arXiv Detail & Related papers (2023-11-17T09:22:28Z) - Implementation of Continuous-Time Quantum Walks on Quantum Computers [0.0]
Quantum walks are interesting candidates to be implemented on quantum computers.
We describe efficient circuits that implement the evolution operator of continuous-time quantum-walk-based search algorithms on three graph classes.
arXiv Detail & Related papers (2022-12-17T14:59:21Z) - 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) - 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) - 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) - Algebraic Compression of Quantum Circuits for Hamiltonian Evolution [52.77024349608834]
Unitary evolution under a time dependent Hamiltonian is a key component of simulation on quantum hardware.
We present an algorithm that compresses the Trotter steps into a single block of quantum gates.
This results in a fixed depth time evolution for certain classes of Hamiltonians.
arXiv Detail & Related papers (2021-08-06T19:38:01Z) - Quantum algorithm for Feynman loop integrals [0.0]
We present a novel benchmark application of a quantum algorithm to Feynman loop integrals.
The two on-shell states of a Feynman propagator are identified with the two states of a qubit.
A quantum algorithm is used to unfold the causal singular configurations of multiloop Feynman diagrams.
arXiv Detail & Related papers (2021-05-18T17:41:56Z) - Information Scrambling in Computationally Complex Quantum Circuits [56.22772134614514]
We experimentally investigate the dynamics of quantum scrambling on a 53-qubit quantum processor.
We show that while operator spreading is captured by an efficient classical model, operator entanglement requires exponentially scaled computational resources to simulate.
arXiv Detail & Related papers (2021-01-21T22:18:49Z) - Quantum walk processes in quantum devices [55.41644538483948]
We study how to represent quantum walk on a graph as a quantum circuit.
Our approach paves way for the efficient implementation of quantum walks algorithms on quantum computers.
arXiv Detail & Related papers (2020-12-28T18:04:16Z)
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.