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

IEEE Nanotechnology Symposium

Dimensionality Reduction of the Complete Bipartite Graph with K Edges Removed for Quantum Walks

Viktoria Koscinski, Chen-Fu Chiang

Published Nov 1, 2018• 1 citation
Publisher

Abstract

Systematic dimensionality reduction allows for the optimization of quantum search and transport problems on particular graphs. In the past, the Lanczos Algorithm has been used to perform systematic dimensionality reduction on matrices of graphs including the Complete Graph (CG), the CG with symmetry broken, and Complete Multipartite Graphs (CMPGs), including the Complete Bipartite Graph (CBG). We focus on expanding the scope of these reductions to the CBG with symmetry broken in order to allow the optimization of Quantum Walks on this type of graph.We show that similarly to the CG, the Lanczos Algorithm can be expanded to the CBG with broken symmetry, which has k random edges removed with the constraints that no more than one edge per node is removed and that no edges that connect to the solution node are removed. Unlike the CG with broken edges, which, after reduction, has 3 types of nodes and a resulting 3×3 matrix, the CBG with broken edges reduces to a graph with 5 types of nodes, resulting in a reduction from an NxN matrix to a 5×5 matrix. From these results, it may be further explored whether or not the more general CMPG reduction may also be expanded by breaking the graph's symmetry, and if so, how the dimensions of the reduced matrices will be affected as the number of partitions grows.

DOI
10.1109/nanotech.2018.8653572

Related papers

Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs

Leonardo Novo, Shantanav Chakraborty, Masoud Mohseni +2 more

Continuous time quantum walks provide an important framework for designing new algorithms and modelling quantum transport and state transfer problems. Often, the graph representing the structure of a problem contains certain symmetries that confine the dynamics to a smaller subspace of the full Hilbert space. In this work, we use invariant subspace methods, that can be computed systematically using the Lanczos algorithm, to obtain the reduced set of states that encompass the dynamics of the problem at hand without the specific knowledge of underlying symmetries. First, we apply this method to obtain new instances of graphs where the spatial quantum search algorithm is optimal: complete graphs with broken links and complete bipartite graphs, in particular, the star graph. These examples show that regularity and high-connectivity are not needed to achieve optimal spatial search. We also show that this method considerably simplifies the calculation of quantum transport efficiencies. Furthermore, we observe improved efficiencies by removing a few links from highly symmetric graphs. Finally, we show that this reduction method also allows us to obtain an upper bound for the fidelity of a single qubit transfer on an XY spin network.

arXiv:1412.7209•Scientific Reports•Sep 2, 2015•89 citations

Quantum Walk on Dimensionality Reduced Complete Bipartite Graphs with k Edges Removed

Chen-Fu Chiang, Aaron Gregory

Due to scalability issue in current quantum technologies, many quantum algorithms can only be implemented for small size problems. Scalability remains a bottleneck for current quantum technologies. For solving real-life size hard problems in the near-term, we explore classes of search graphs that can be efficiently reduced to a implementable scale for many quantum algorithms. The reduced Hamiltonian preserves the dynamics of the original Hamiltonian. One of the quantum algorithms we choose for the reduced Hamiltonian is continuous time quantum walk (CTQW). We further show how to determine the correct value of the coupling factor of the underlying CTQW. With wrong couple factor values, the optimality (quadratic speedup) from CTQW might be lost. In this work, we extend the class of reducible graphs to complete bipartite graphs with random $k$ edges removed. We further demonstrate through mathematical proof and simulation experiment using IBM Qiskit to show that the quadratic speed-up is preserved for the CTQW.

IEEE Globecom Workshops (GC Wkshps)•Dec 1, 2019•1 citation

Continuous-time quantum walks on directed bipartite graphs

Beat Tödtli, Monika Laner, Jouri Semenov +3 more

This paper investigates continuous-time quantum walks on directed bipartite graphs based on a graph's adjacency matrix. We prove that on bipartite graphs, probability transport between the two node partitions can be completely suppressed by tuning a model parameter $\ensuremath{\alpha}$. We provide analytic solutions to the quantum walks for the star and circulant graph classes that are valid for an arbitrary value of the number of nodes $N$, time $t$, and the model parameter $\ensuremath{\alpha}$. We discuss quantitative and qualitative aspects of quantum walks based on directed graphs and their undirected counterparts. Numerical simulations of quantum walks on circulant graphs show complex interference phenomena and how complete suppression of transport is achieved near $\ensuremath{\alpha}=\ensuremath{\pi}/2$. By proving two mirror symmetries around $\ensuremath{\alpha}=0$ and $\ensuremath{\pi}/2$ we show that these quantum walks have a period of $\ensuremath{\pi}$ in $\ensuremath{\alpha}$. We show that undirected edges lose their effect on the quantum walk at $\ensuremath{\alpha}=\ensuremath{\pi}/2$ and present non-bipartite graphs that exhibit suppression of transport. Finally, we analytically compute the Hamiltonians of quantum walks on the directed ring graph.

arXiv:1606.00992•Physical Review A•Nov 30, 2016•9 citations

Symmetric Reduction Techniques for Quantum Graph Colouring

Lord Sen, Shyamapada Mukherjee

This paper introduces an efficient quantum computing method for reducing special graphs in the context of the graph coloring problem. The special graphs considered include both symmetric and non-symmetric graphs where the axis passes through nodes only, edges only, and both together. The presented method reduces the number of coloring matrices, which is important for realization of the number of quantum states required, from $K^{N}$ to $K^{\frac{N+m}{2}}$ upon one symmetric reduction of graphs symmetric about an axis passing through $m$ nodes, where $K$ is the number of colours required and \emph{N} being total number of nodes. Similarly for other types also, the number of quantum states is reduced. The complexity in the number of qubits has been reduced by $δC_q= \frac{9N^2}{8}-\frac{3m^2}{8}-\frac{3Nm}{4}-\frac{N}{4}+\frac{m}{4}$ upon one symmetric reduction of graphs, symmetric about an axis passing through $m$ nodes and other types as presented in the paper. Additionally, the number of gates and number of iterations are reduced massively compared to state-of-the-art quantum algorithms. Like for a graph with 20 nodes and symmetric line passing through 2 nodes, the number of iterations decreased from 5157 to 67. Therefore, the procedure presented for solving the graph coloring problem now requires a significantly reduced number of qubits compared to before. The run time of the proposed algorithm for these special type of graphs are reduced from $O(1.9575^{N})$ to $O(1.9575^{(\frac{N+m}{2})})$ upon one symmetric reduction of graphs symmetric about an axis passing through $m$ nodes and similarly for others cases.

arXiv:2510.16784•Oct 19, 2025•0 citations

Quantum walks on highly symmetric graphs

Mark S. Hillery

We study discrete-time quantum walks on the complete and bipartite graphs. We show how they can be used to perform searches. The symmetry of these graphs leads to a significant dimensional reduction of the problem.

International Conference on Quantum Information•Jan 1, 2008•0 citations

Spatial Search by Nonlinear Quantum Walk

David A. Meyer, Thomas G. Wong

Many-body quantum systems with effective nonlinearities have been shown to speed up quantum search on the complete graph, \textit{i.e.}, the combinatorial version of Grover's algorithm, at the expense of the number of particles needed for the effective nonlinearity to hold. Physically, however, data may not be arranged in an all-to-all network, and the task of searching incomplete graphs is the spatial search problem. We explore spatial search using a continuous-time nonlinear quantum walk on a variety of graphs. First, we consider incomplete graphs that are ``sufficiently complete'' so as to asymptotically search like the complete graph under a continuous-time (linear) quantum walk, which includes strongly regular graphs such as Paley graphs, regular graphs such as hypercubes, and irregular graphs such as complete bipartite graphs. For these sufficiently complete graphs, we analytically prove nonlinear speedups for Paley graphs and for complete bipartite graphs whose two partite sets both have size $Θ(N)$, for suitable cubic and cubic-quintic nonlinearities, and we give numerical evidence for stronger nonlinearities and for hypercubes. Second, we explore arbitrary-dimensional cubic lattices, and we numerically show that certain nonlinearities speed up search on sufficiently high dimensional lattices. Thus, nonlinear quantum search can remain viable even when the underlying graph is incomplete.

quant-pharXiv:2606.01403•Jun 2, 2026•0 citations
Systematic dimensionality reduction allows for the optimization of quantum search and transport problems on particular graphs. In the past, the Lanczos Algorithm has been used to perform systematic dimensionality reduction on matrices of graphs including the Complete Graph (CG), the CG with symmetry broken, and Complete Multipartite Graphs (CMPGs), including the Complete Bipartite Graph (CBG). We focus on expanding the scope of these reductions to the CBG with symmetry broken in order to allow the optimization of Quantum Walks on this type of graph.We show that similarly to the CG, the Lanczos Algorithm can be expanded to the CBG with broken symmetry, which has k random edges removed with the constraints that no more than one edge per node is removed and that no edges that connect to the solution node are removed. Unlike the CG with broken edges, which, after reduction, has 3 types of nodes and a resulting 3×3 matrix, the CBG with broken edges reduces to a graph with 5 types of nodes, resulting in a reduction from an NxN matrix to a 5×5 matrix. From these results, it may be further explored whether or not the more general CMPG reduction may also be expanded by breaking the graph's symmetry, and if so, how the dimensions of the reduced matrices will be affected as the number of partitions grows.
Continuous time quantum walks provide an important framework for designing new algorithms and modelling quantum transport and state transfer problems. Often, the graph representing the structure of a problem contains certain symmetries that confine the dynamics to a smaller subspace of the full Hilbert space. In this work, we use invariant subspace methods, that can be computed systematically using the Lanczos algorithm, to obtain the reduced set of states that encompass the dynamics of the problem at hand without the specific knowledge of underlying symmetries. First, we apply this method to obtain new instances of graphs where the spatial quantum search algorithm is optimal: complete graphs with broken links and complete bipartite graphs, in particular, the star graph. These examples show that regularity and high-connectivity are not needed to achieve optimal spatial search. We also show that this method considerably simplifies the calculation of quantum transport efficiencies. Furthermore, we observe improved efficiencies by removing a few links from highly symmetric graphs. Finally, we show that this reduction method also allows us to obtain an upper bound for the fidelity of a single qubit transfer on an XY spin network.
Due to scalability issue in current quantum technologies, many quantum algorithms can only be implemented for small size problems. Scalability remains a bottleneck for current quantum technologies. For solving real-life size hard problems in the near-term, we explore classes of search graphs that can be efficiently reduced to a implementable scale for many quantum algorithms. The reduced Hamiltonian preserves the dynamics of the original Hamiltonian. One of the quantum algorithms we choose for the reduced Hamiltonian is continuous time quantum walk (CTQW). We further show how to determine the correct value of the coupling factor of the underlying CTQW. With wrong couple factor values, the optimality (quadratic speedup) from CTQW might be lost. In this work, we extend the class of reducible graphs to complete bipartite graphs with random kkk edges removed. We further demonstrate through mathematical proof and simulation experiment using IBM Qiskit to show that the quadratic speed-up is preserved for the CTQW.
This paper investigates continuous-time quantum walks on directed bipartite graphs based on a graph's adjacency matrix. We prove that on bipartite graphs, probability transport between the two node partitions can be completely suppressed by tuning a model parameter $\ensuremath{\alpha}$. We provide analytic solutions to the quantum walks for the star and circulant graph classes that are valid for an arbitrary value of the number of nodes NNN, time ttt, and the model parameter $\ensuremath{\alpha}$. We discuss quantitative and qualitative aspects of quantum walks based on directed graphs and their undirected counterparts. Numerical simulations of quantum walks on circulant graphs show complex interference phenomena and how complete suppression of transport is achieved near $\ensuremath{\alpha}=\ensuremath{\pi}/2$. By proving two mirror symmetries around $\ensuremath{\alpha}=0$ and $\ensuremath{\pi}/2$ we show that these quantum walks have a period of $\ensuremath{\pi}$ in $\ensuremath{\alpha}$. We show that undirected edges lose their effect on the quantum walk at $\ensuremath{\alpha}=\ensuremath{\pi}/2$ and present non-bipartite graphs that exhibit suppression of transport. Finally, we analytically compute the Hamiltonians of quantum walks on the directed ring graph.
This paper introduces an efficient quantum computing method for reducing special graphs in the context of the graph coloring problem. The special graphs considered include both symmetric and non-symmetric graphs where the axis passes through nodes only, edges only, and both together. The presented method reduces the number of coloring matrices, which is important for realization of the number of quantum states required, from KNK^{N}KN to KN+m2K^{\frac{N+m}{2}}K2N+m​ upon one symmetric reduction of graphs symmetric about an axis passing through mmm nodes, where KKK is the number of colours required and \emph{N} being total number of nodes. Similarly for other types also, the number of quantum states is reduced. The complexity in the number of qubits has been reduced by δCq=9N28−3m28−3Nm4−N4+m4δC_q= \frac{9N^2}{8}-\frac{3m^2}{8}-\frac{3Nm}{4}-\frac{N}{4}+\frac{m}{4}δCq​=89N2​−83m2​−43Nm​−4N​+4m​ upon one symmetric reduction of graphs, symmetric about an axis passing through mmm nodes and other types as presented in the paper. Additionally, the number of gates and number of iterations are reduced massively compared to state-of-the-art quantum algorithms. Like for a graph with 20 nodes and symmetric line passing through 2 nodes, the number of iterations decreased from 5157 to 67. Therefore, the procedure presented for solving the graph coloring problem now requires a significantly reduced number of qubits compared to before. The run time of the proposed algorithm for these special type of graphs are reduced from O(1.9575N)O(1.9575^{N})O(1.9575N) to O(1.9575(N+m2))O(1.9575^{(\frac{N+m}{2})})O(1.9575(2N+m​)) upon one symmetric reduction of graphs symmetric about an axis passing through mmm nodes and similarly for others cases.
Many-body quantum systems with effective nonlinearities have been shown to speed up quantum search on the complete graph, \textit{i.e.}, the combinatorial version of Grover's algorithm, at the expense of the number of particles needed for the effective nonlinearity to hold. Physically, however, data may not be arranged in an all-to-all network, and the task of searching incomplete graphs is the spatial search problem. We explore spatial search using a continuous-time nonlinear quantum walk on a variety of graphs. First, we consider incomplete graphs that are ``sufficiently complete'' so as to asymptotically search like the complete graph under a continuous-time (linear) quantum walk, which includes strongly regular graphs such as Paley graphs, regular graphs such as hypercubes, and irregular graphs such as complete bipartite graphs. For these sufficiently complete graphs, we analytically prove nonlinear speedups for Paley graphs and for complete bipartite graphs whose two partite sets both have size Θ(N)Θ(N)Θ(N), for suitable cubic and cubic-quintic nonlinearities, and we give numerical evidence for stronger nonlinearities and for hypercubes. Second, we explore arbitrary-dimensional cubic lattices, and we numerically show that certain nonlinearities speed up search on sufficiently high dimensional lattices. Thus, nonlinear quantum search can remain viable even when the underlying graph is incomplete.