Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Advances in intelligent systems and computing

Circuit Synthesis of Marked Clique Problem using Quantum Walk

Arpita Sanyal, Amit Saha, Bipulan Gain, Sudhindu Bikash Mandal

Published Jan 1, 2017• 0 citations
Publisher
DOI
10.1007/978-981-10-3409-1_3

Related papers

Circuit Design Of Clique Problem And Its Implementation On NISQ Using Combinatorial Approach Of Classical-Quantum Hybrid Model

Arpita Sanyal, Amit Saha, Banani Saha +1 more

•Mar 1, 2020•2 citations

Searching weighted barbell graphs with Laplacian and adjacency quantum walks

Jonas Duda, Thomas G. Wong

A quantum particle evolving by Schr\"odinger's equation in discrete space constitutes a continuous-time quantum walk on a graph of vertices and edges. When a vertex is marked by an oracle, the quantum walk effects a quantum search algorithm. Previous investigations of this quantum search algorithm on graphs with cliques have shown that the edges between the cliques can be weighted to enhance the movement of probability between the cliques to reach the marked vertex. In this paper, we explore the most restrictive form of this by analyzing search on a weighted barbell graph that consists of two cliques of the same size joined by a single weighted edge or bridge. This graph is generally irregular, so quantum walks governed by the graph Laplacian or by the adjacency matrix can differ. We show that the Laplacian quantum walk's behavior does not change, no matter the weight of the bridge, and so the single bridge is too restrictive to affect the walk. Similarly, the adjacency quantum walk's behavior is unchanged for most weights, but when the weight equals the size of a clique, the probability does collect at the clique containing the marked vertex, and utilizing a two-stage algorithm with different weights for each stage, the success probability is boosted from 0.5 to 0.996, independent of the size of the barbell graph.

arXiv:2408.08244•Physical Review A•Oct 15, 2024•2 citations

Quantum Circuit Compilation for the Graph Coloring Problem

Angelo Oddi, Riccardo Rasconi, Marco Baioletti +2 more

Lecture notes in computer science•Jan 1, 2023•3 citations

Quantum circuit synthesis with diffusion models

Florian Fürrutter, Gorka Muñoz-Gil, Hans J. Briegel

arXiv:2311.02041•Nature Machine Intelligence•May 20, 2024•63 citations

Searching via walking: How to find a marked clique of a complete graph using quantum walks

Mark S. Hillery, Daniel Reitzner, Vladimír Bužek

We show how a quantum walk can be used to find a marked edge or a marked complete subgraph of a complete graph. We employ a version of a quantum walk, the scattering walk, which lends itself to experimental implementation. The edges are marked by adding elements to them that impart a specific phase shift to the particle as it enters or leaves the edge. If the complete graph has $N$ vertices and the subgraph has $K$ vertices, the particle becomes localized on the subgraph in $O(N/K)$ steps. This leads to a quantum search that is quadratically faster than a corresponding classical search. We show how to implement the quantum walk using a quantum circuit and a quantum oracle, which allows us to specify the resources needed for a quantitative comparison of the efficiency of classical and quantum searches---the number of oracle calls.

arXiv:0911.1102•Physical Review A•Jun 17, 2010•39 citations

Discrete-time quantum walks and graph structures

Chris D. Godsil, Hanmeng Zhan

arXiv:1701.04474•Journal of Combinatorial Theory Series A•May 16, 2019•33 citations
A quantum particle evolving by Schr\"odinger's equation in discrete space constitutes a continuous-time quantum walk on a graph of vertices and edges. When a vertex is marked by an oracle, the quantum walk effects a quantum search algorithm. Previous investigations of this quantum search algorithm on graphs with cliques have shown that the edges between the cliques can be weighted to enhance the movement of probability between the cliques to reach the marked vertex. In this paper, we explore the most restrictive form of this by analyzing search on a weighted barbell graph that consists of two cliques of the same size joined by a single weighted edge or bridge. This graph is generally irregular, so quantum walks governed by the graph Laplacian or by the adjacency matrix can differ. We show that the Laplacian quantum walk's behavior does not change, no matter the weight of the bridge, and so the single bridge is too restrictive to affect the walk. Similarly, the adjacency quantum walk's behavior is unchanged for most weights, but when the weight equals the size of a clique, the probability does collect at the clique containing the marked vertex, and utilizing a two-stage algorithm with different weights for each stage, the success probability is boosted from 0.5 to 0.996, independent of the size of the barbell graph.
We show how a quantum walk can be used to find a marked edge or a marked complete subgraph of a complete graph. We employ a version of a quantum walk, the scattering walk, which lends itself to experimental implementation. The edges are marked by adding elements to them that impart a specific phase shift to the particle as it enters or leaves the edge. If the complete graph has NNN vertices and the subgraph has KKK vertices, the particle becomes localized on the subgraph in O(N/K)O(N/K)O(N/K) steps. This leads to a quantum search that is quadratically faster than a corresponding classical search. We show how to implement the quantum walk using a quantum circuit and a quantum oracle, which allows us to specify the resources needed for a quantitative comparison of the efficiency of classical and quantum searches---the number of oracle calls.