WorksPhysics and Astronomy
Hardware-Aware Realization of Deterministic Quantum-Walk Search on Complete Bipartite Graphs
Abstract
Complete bipartite graphs offer a canonical platform for deterministic quantum search with quadratic speedup. We report the first experimental realization of deterministic discrete-time quantum-walk search over complete bipartite graphs, enabled by high-fidelity operations and a dynamical-phase compensation scheme, using a digital gate-based processor rather than an evolution-based platform. By compiling the search circuits to the native gate set and square-lattice topology, we implement full-space encoding to realize instances of graph sizes and , with success probabilities of 97.6% and 70.8% for finding the marked vertex, respectively. We also realize resource-efficient exact instances up to size , the largest achieving 66% success probability. Separately, a reduced invariant-subspace encoding preserves the dynamics of the deterministic search algorithm on two qubits for nominal problem sizes up to , with the success probability approaching 50%. Resource analyses of logical, hardware-compiled, and fault-tolerant-gate-set-synthesized circuits show that circuit depth and size scale as , with hardware overheads entering only as constant prefactors. For application-scale graphs (), an effective gate-fidelity model requires per-gate infidelity near . These results establish a concrete algorithm-to-hardware pathway for deterministic structured quantum search on gate-based quantum processors.
Introduction—
Complete bipartite graphs model two-mode interaction systems across recommendation, biological, and quantum spin networks, where the absence of intra-class edges imposes a spectral symmetry shaping all dynamical processes, while bipartition and marked-set asymmetry yield richer interference dynamics that better reflect structured real-world systems [1, 2]. Although complete bipartite graphs are highly symmetric, bipartite quadratic assignment problem-type problems remain NP-hard on them [3]. This motivates our study of search algorithms for complete bipartite graphs.
Quantum walks, realized in continuous and discrete forms across platforms [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16], achieve quadratic and even exponential speedups for certain structured search problems [17, 18, 19, 20, 21, 22, 23, 24]. Yet their success probabilities oscillate, preventing deterministic retrieval, which motivates schemes concentrating all probability at a prescribed time. Such ideas are well developed for Grover-type search [25, 26] and extended to several continuous-time quantum-walk (CTQW) models [27, 28, 29]. However, CTQW’s Hamiltonian formulation aligns less naturally with gate-based, fault-tolerant computing, whereas discrete-time quantum-walk (DTQW) maps directly to circuits. DTQW achieves deterministic search on complete graphs [25, 26], but this does not transfer to complete bipartite graphs, where bipartition and marked-set asymmetry break the simple two-state dynamics. Building on this, a recent deterministic DTQW search algorithm [30] overcomes the obstacle using a generalized Grover coin and a tunable phase oracle, mapping the dynamics onto an effective four-state (or eight-state) model and concentrating all probability on the marked vertex at a prescribed time, thereby achieving unit success probability with quadratic speedup.
Nevertheless, translating this ideal algorithm into executable circuits on gate-based hardware is nontrivial, requiring edge-space encoding, oracle and coin synthesis, conditional-shift implementation, hardware compilation and fidelity analysis.
We validate this full pipeline on the gate-based hardware [31], compiling the resulting circuits to the native gate set and square-lattice topology to analyze how circuit depth, gate count, and required gate fidelity scale with graph size.
We then report the first experimental realization of quantum-walk search on a complete bipartite graph, with a success probability exceeding the same-query classical baseline [32] at graph size , and introduce a reduced invariant-subspace encoding that extends the accessible range on two qubits for the scalability benchmark. Together, these results identify circuit depth and accumulated gate errors—not Hilbert-space dimension alone—as the dominant scaling bottleneck. This work establishes an explicit algorithm-to-hardware pathway for structured quantum search on future processors.
Algorithm Setting and Circuit Construction—
The deterministic search protocol is naturally formulated as a discrete-time quantum walk on the edge space of a complete bipartite graph. Following Ref. [30], we consider as a complete bipartite graph with vertex partition , where and . The walk acts on the edge Hilbert space spanned by .
The one-step walk search operator is , with the coin operator and , where and represents the degree of vertex . The conditional shift satisfies , and the oracle acts as
for marked set .
With and known, the following four states span a -invariant subspace:
With appropriate parameters , the initial state evolves to unit success probability after walk steps [30].
As a practical motivation, the National Resident Matching Program (NRMP) [33, 34] maps naturally onto a complete bipartite graph, with applicants and residency positions as the two vertex sets, as shown in Figure 1(a). Locating a marked applicant or position is therefore a structured-search task on this graph. We assess the viability of the deterministic DTQW protocol by estimating the resources required after hardware compilation and running the hardware-compiled circuits of Figure 1(c) on the quantum experiment platform depicted in Figure 1(b), including both the general full-space encoding and the exact resource-efficient instance.
Figure 1. Overview of the experimental platform and algorithm implementation. (a) Schematic representation of embedding an NRMP problem into a complete bipartite graph, where the top nodes represent all active applicants and the bottom nodes represent all available positions. (b) Square-lattice topology and physical qubit connectivity of the quantum processor used in this work. (c) Full algorithmic quantum circuits for the general and special cases.
Resource scaling and gate-fidelity requirements—
To assess the practical feasibility of the deterministic DTQW search algorithm, we analyze how its resource cost grows with graph size after realistic hardware compilation. We focus on the general full-space construction, since it directly realizes the original search problem and therefore governs the asymptotic cost. The special case, by contrast, has a fixed circuit structure and does not probe the same bottleneck. For this analysis we adopt the balanced encoding , giving a total size , where is the bit length of one partition and is distinct from the marked-set size . The vertex/edge-register encoding and the oracle, coin, and shift definitions are detailed in the Supplemental Material [35].
To distinguish algorithmic scaling from hardware overhead, we compare three circuit representations up to () in Figure 2(a,Figure 2b). The logical circuit has no connectivity constraint; the hardware-compiled circuit uses square-lattice connectivity and the native gate set ; and the SK-synthesized circuit further applies Solovay–Kitaev (SK) synthesis [36] over , retaining CZ gates. The last stage projects resources for fault-tolerant implementations, excluding error-correction overhead; experiments use hardware-compiled circuits without SK synthesis. Multicontrolled phase rotations dominate each walk step, requiring depth and gates [37]. With search iterations, both total depth and size scale as up to logarithmic factors. Over the investigated range, hardware compilation increases depth by a factor of 4–5 and size by 5–6, while SK synthesis adds a further factor of about 2 to both, preserving the leading scaling.
Figure 2. Resource scaling and gate-fidelity requirements for the general complete-bipartite graph search circuit. (a) Circuit depth versus graph size for the logical circuit, the hardware-compiled circuit mapped to the square-lattice topology and native gate set, and the SK-synthesized circuit obtained by subsequent Solovay–Kitaev (SK) synthesis. (b) Corresponding circuit size versus graph size. (c) Required per-gate infidelity, , versus graph size under , estimated from fitted gate-count models for the logical and SK-synthesized circuits; the vertical dashed line indicates the current Zuchongzhi 3.1 graph-size limit estimated from calibrated one- and two-qubit gate fidelities using the effective gate-fidelity model.
Because a direct success-rate estimation becomes intractable at large , we use the total circuit fidelity as a scalable proxy for the hardware requirement, where is the effective elementary-gate fidelity and is a fitted gate count obeying . Taking as an order-unity criterion, the comparison in Figure 2(c) shows that hardware compilation and SK synthesis tighten the required per-gate infidelity by roughly an order of magnitude relative to the logical estimate. Applying this model to the calibrated fidelities places the current device at only a small graph size, as marked by the vertical dashed line in Figure 2(c), confirming that present hardware only supports proof-of-principle full-space demonstrations. Reaching application scale is far more demanding. A graph size , matching the latest NRMP instance [33, 34], already requires a per-gate infidelity near , and requires the level, setting concrete logical-gate performance targets for fault-tolerant implementations.
Experimental Results—
Following the circuit-level resource analysis, we implement both the general full-space circuit and the resource-efficient special-case circuit on the superconducting quantum processor. The logical walk operator is compiled into the native gate set consisting of single-qubit rotations and CZ gates, with circuit depth increasing with graph size. We experimentally realize circuits involving up to seven qubits, corresponding to a graph size of . To mitigate dephasing during long idle periods, dynamical-decoupling pulses are inserted throughout circuit execution. We further calibrate and compensate the dynamical phases induced by transient effects of the CZ control pulses using virtual- corrections, as detailed in the Supplemental Material [35].
In the general case, we performed search experiments for graph sizes and , with the results shown in Figure 3(a) and (b), respectively. In both instances, the success probability increases with the number of walk steps, reaching final values of 97.6% and 70.8%, respectively. For the case, the measured success probability exhibits a sharp increase after and surpasses the classical success probability [32] in the final two steps, as shown in Figure 3(b), where denotes the number of oracle queries and is the graph size. These results demonstrate the effective accumulation of probability amplitude on the target vertex and provide a proof-of-principle experimental validation of deterministic full-space search on complete bipartite graphs, whose ideal success probability reaches unity. Scaling the general construction to already requires 743 CZ layers, exceeding the reliable depth of the present control hardware. This implementation limit is consistent with the resource analysis of Figure 2, where the hardware-compiled circuit depth is identified
Figure 3. Experimental realizations of deterministic DTQW search on complete bipartite graphs. Panels (a) and (b) correspond to the general case with graph sizes and , respectively, and panels (c) and (d) correspond to the special case with and , respectively. The processor layouts indicate the qubits and couplers of the Zuchongzhi 3.1 processor used in each experiment. The probability plots show the target-vertex success probability versus walk step; dashed lines denote theoretical predictions, symbols denote experimental data, and error bars represent one standard deviation estimated from measurement shots. The dash-dotted line in (b) denotes the classical success probability . The colored complete-bipartite graphs show the vertex probability distributions at successive steps for the general case and at the final step for the special case.
as the dominant scaling overhead. The corresponding experiment was therefore not performed. This limitation identifies circuit depth and accumulated gate errors as the main bottlenecks for extending the direct full-space implementation to larger graphs.
For the special case , the logical circuit consists of an initial layer of Hadamard gates on the vertex and edge registers, followed by the fixed sequence , as shown in Figure 1(c). We demonstrated search experiments for graph sizes and 16, yielding final success probabilities of 70.3% and 66.0%, respectively, as shown in Figure 3(c) and (d). Notably, the success probability in this case does not decrease significantly with increasing graph size. Together with the resource analysis of the general case, these results indicate that the principal limitation to scaling arises not merely from the growth of Hilbert-space dimension, but more critically from the accompanying increase in circuit depth. By substantially mitigating this depth overhead, the special-case construction provides a promising route toward scalable implementations of deterministic DTQW search on larger gate-based quantum processors.
Reduced-subspace scalability benchmark—
To further benchmark experimental scalability beyond the graph sizes accessible to the direct full-space encoding, we introduce the reduced-subspace construction illustrated in Figure 4(a) as an effective-size probe of the target walk dynamics. Although this construction does not encode all graph vertices explicitly, it faithfully reproduces the effective search dynamics of the original walk within its invariant subspace. It therefore provides a controlled way to test how the deterministic interference mechanism behaves as the nominal graph size and the corresponding walk schedule increase.
Figure 4. Reduced-subspace demonstration of scalable complete-bipartite DTQW search dynamics. (a) Subspace reduction via class aggregation from the original complete bipartite graph (left) to an effective three-vertex representation (right). (b) Quantum circuit for the reduced-subspace implementation. (c) Target-vertex success probability versus walk step for graph sizes (), as indicated by the gray labels. Red dashed lines denote theoretical predictions, blue symbols denote experimental data, and green dash-dotted lines denote classical success probability . Error bars represent one standard deviation estimated from measurement shots.
In this setting, the walk is restricted to the four-dimensional invariant subspace spanned by introduced above, so the evolution can be represented with two qubits, independent of the graph size. This reduced construction provides a compact setting for benchmarking the target walk dynamics and diagnosing hardware errors. Following the parameter schedule of [30], we construct a state-preparation block followed by a sequence of walk steps implementing on the reduced space. The corresponding logical circuit is shown in Figure 4(b).
In the subspace case, we clearly observe the search success probability rising as the number of walk steps increases for nominal graph sizes from to , as shown in Figure 4(c). Specifically, the success probability for reaches 90%, and for , , and , it remains around 80%, showing that the deterministic-search population transfer is preserved over a range of effective graph sizes. At larger nominal sizes, the deeper walk schedules lead to a gradual reduction of the peak probability, reaching about 60% for and approaching 50% for , where decoherence drives the output close to a mixed state. These results indicate that the protocol is experimentally viable at the circuit level and that its effective search dynamics can be preserved over larger nominal graph sizes when the full encoding overhead is removed.
Conclusion—
We have demonstrated deterministic discrete-time quantum-walk search on complete bipartite graphs using a gate-based digital processor. By combining full-space and invariant-subspace encodings, we preserve exact search dynamics across a wide range of effective graph sizes, while our resource analysis identifies accumulated gate errors—rather than problem size alone—as the central scaling bottleneck. This establishes a concrete algorithm-to-hardware pathway for structured quantum search and motivates low-error gate synthesis and error mitigation for application-scale implementations.
Acknowledgments—
This research was supported by the Quantum Science and Technology–National Science and Technology Major Project (Grant No. 2024ZD0300500); the Quantum Science and Technology-National Science and Technology Major Project (Grant No. 2021ZD0300200); the National Natural Science Foundation of China (Grant Nos. 92476203, 92476001, 62325210, and 62301531); the New Cornerstone Science Foundation through the XPLORER PRIZE; the Jinan Science and Technology Bureau and the Jinan High-Tech Zone Management Committee; the Cultivation Project of the Shanghai Research Center for Quantum Sciences (Grant No. LZPY2024); the Beijing Natural Science Foundation (Grant No. 4252012); and the Taishan Scholars Program.
References
References
- [1]S. Cambie and R. Hämäläinen, Packing colourings in complete bipartite graphs and the inverse problem for correspondence packing, Journal of Graph Theory 109, 52 (2025).arxiv.org/abs/2303.01944
- [2]Z. J. Bara, R. A. Rasid, and R. G. Artes Jr, Independent vertex neighborhood polynomials: Behavior of graphs and some applications, Advances & Applications in Discrete Mathematics 42, 47 (2025).DOI
- [3]A. P. Punnnen and Y. Wang, The bipartite quadratic assignment problem and extensions, European Journal of Operational Research 250, 715 (2016).DOI
- [4]C. A. Ryan, M. Laforest, J.-C. Boileau, and R. Laflamme, Experimental implementation of a discrete-time quantum random walk on an NMR quantum-information processor, Physical Review A—Atomic, Molecular, and Optical Physics 72, 062317 (2005).DOI
- [5]D. Lu, J. Zhu, P. Zou, X. Peng, Y. Yu, S. Zhang, Q. Chen, and J. Du, Experimental implementation of a quantum random-walk search algorithm using strongly dipolar coupled spins, Physical Review A—Atomic, Molecular, and Optical Physics 81, 022308 (2010).DOI
- [6]M. Gräfe, R. Heilmann, M. Leubgue, D. Guzman-Silva, A. Perez-Leija, and A. Szameit, Integrated photonic quantum walks, Journal of Optics 18, 103002 (2016).
- [7]L. Neves and G. Puentes, Photonic discrete-time quantum walks and applications, Entropy 20, 731 (2018).DOI
- [8]Z. Yan, Y.-R. Zhang, M. Gong, Y. Wu, Y. Zheng, S. Li, C. Wang, F. Liang, J. Lin, Y. Xu, et al., Strongly cor- related quantum walks with a 12-qubit superconducting processor, Science 364, 753 (2019).
- [9]M. Gong, S. Wang, C. Zha, M.-C. Chen, H.-L. Huang, Y. Wu, Q. Zhu, Y. Zhao, S. Li, S. Guo, et al., Quantum walks on a programmable two-dimensional 62-qubit superconducting processor, Science 372, 948 (2021).DOI
- [10]K. Zhou, J.-W. Xu, Q.-P. Su, Y. Zhang, X.-M. Yu, Z. Ma, H.-Y. Zhang, H.-Y. Shi, W. Zheng, S. Pan, et al., Demonstration of discrete-time quantum walks and observation of topological edge states in a superconducting qubit chain, Physical Review Letters 135, 250601 (2025).DOI
- [11]V. Dubovitskii, F. Utro, A. Bose, L. Parida, S. Maniscalco, and S. N. Filippov, Experimental implementation of a discrete-time quantum walk on biological networks, arXiv preprint arXiv:2602.24053 (2026).DOI
- [12]L. Razzoli, G. Cenedese, M. Bondani, and G. Benenti, Efficient implementation of discrete-time quantum walks on quantum computers, Entropy 26, 313 (2024).DOI
- [13]A. Shakeel, Efficient and scalable quantum walk algorithms via the quantum Fourier transform, Quantum Information Processing 19, 323 (2020).DOI
- [14]K. Georgopoulos, C. Emary, and P. Zuliani, Comparison of quantum-walk implementations on noisy intermediate-scale quantum computers, Physical Review A 103, 022408 (2021).DOI
- [15]A. Wing-Bocanegra and S. E. Venegas-Andraca, Circuit implementation of discrete-time quantum walks via the shunt decomposition method, Quantum Information Processing 22, 146 (2023).
- [16]V. Wadhia, N. Chancellor, and V. Kendon, Cycle discrete-time quantum walks on a noisy quantum computer, The European Physical Journal D 78, 29 (2024).
- [17]D. Aharonov, A. Ambainis, J. Kempe, and U. Vazirani, Quantum walks on graphs, in Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing (ACM, New York, NY, USA, 2001) pp. 50–59.
- [18]A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, Exponential algorithmic speedup by a quantum walk, in Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (2003) pp. 59–68.
- [19]A. M. Childs and J. Goldstone, Spatial search by quantum walk, Physical Review A 70, 022314 (2004).DOI
- [20]S. Chakraborty, L. Novo, A. Ambainis, and Y. Omar, Spatial search by quantum walk is optimal for almost all graphs, Physical Review Letters 116, 100501 (2016).DOI
- [21]A. Ambainis, A. Gil yén, S. Jeffery, and D. Kokiānis, Quadratic speedup for finding marked vertices by quantum walks, in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (ACM, New York, NY, USA, 2020) pp. 1119–1132.arxiv.org/abs/1903.07493
- [22]S. Apers, S. Chakraborty, L. Novo, and J. Roland, Quadratic speedup for spatial search by continuous-time quantum walk, Physical Review Letters 129, 160502 (2022).DOI
- [23]F. Peng, M. Li, and X. Sun, Search algorithm on strongly regular graph by lackadaisical quantum walk, Journal of Physics A: Mathematical and Theoretical 57, 135301 (2024).DOI
- [24]F. Peng, M. Li, and X. Sun, Lackadaisical discrete-time quantum walk on Johnson graph, Physica A: Statistical Mechanics and its Applications 635, 129495 (2024).DOI
- [25]P. Høyer, Arbitrary phases in quantum amplitude amplification, Physical Review A 62, 052304 (2000).DOI
- [26]G.-L. Long, Grover algorithm with zero theoretical failure rate, Physical Review A 64, 022307 (2001).DOI
- [27]S. Marsh and J. B. Wang, Deterministic spatial search using alternating quantum walks, Physical Review A 104, 022216 (2021).DOI
- [28]D. Qu, S. Marsh, K. Wang, L. Xiao, J. Wang, and P. Xue, Deterministic search on star graphs via quantum walks, Physical Review Letters 128, 050501 (2022).DOI
- [29]Q. Wang, Y. Jiang, S. Feng, and L. Li, Unifying quantum spatial search, state transfer, and uniform sampling on graphs, Physical Review A 111, 042608 (2025).DOI
- [30]F. Peng, M. Li, and X. Sun, Deterministic discrete-time quantum walk search on complete bipartite graphs, Physical Review Research 6, 033042 (2024).DOI
- [31]T. Jiang, J. Cai, J. Huang, N. Zhou, Y. Zhang, J. Bei, G. Cai, S. Cao, F. Chen, J. Chen, K. Chen, X. Chen, X. Chen, Z. Chen, Z. Chen, W. Chu, H. Deng, Z. Deng, P. Ding, X. Ding, Z. Ding, S. Dong, B. Fan, D. Fan, Y. Fu, D. Gao, L. Ge, J. Gui, C. Guo, S. Guo, X. Guo, L. Han, T. He, L. Hong, Y. Hu, H.-L. Huang, Y.-H. Huo, Z. Jiang, H. Jin, Y. Leng, D. Li, D. Li, F. Li, J. Li, J. Li, J. Li, N. Li, S. Li, W. Li, Y. Li, Y. Li, F. Liang, X. Liang, N. Liao, J. Lin, W. Lin, D. Liu, H. Liu, M. Liu, X. Liu, X. Liu, Y. Liu, H. Lou, Y. Ma, L. Meng, H. Mou, K. Nan, B. Nie, M. Nie, J. Ning, L. Niu, W. Peng, H. Qian, H. Rong, T. Rong, H. Shen, Q. Shen, H. Su, F. Su, C. Sun, L. Sun, T. Sun, Y. Sun, Y. Tan, J. Tan, L. Tang, W. Tu, J. Wang, B. Wang, C. Wang, C. Wang, C. Wang, J. Wang, L. Wang, R. Wang, S. Wang, X. Wang, X. Wang, X. Wang, Y. Wang, Z. Wei, J. Wei, D. Wu, G. Wu, X. J. Wu, Y. Wu, S. Xie, L. Xin, Y. Xu, C. Xue, K. Yan, W. Yang, X. Yang, Y. Yang, Y. Ye, Z. Ye, C. Ying, J. Yu, Q. Yu, W. Yu, X. Zeng, C. Zha, S. Zhan, F. Zhang, H. Zhang, K. Zhang, W. Zhang, Y. Zhang, Y. Zhang, L. Zhang, G. Zhao, P. Zhao, X. Zhao, Y. Zhao, Z. Zhao, L. Zheng, F. Zhou, L. Zhou, N. Zhou, S. Zhou, Z. Zhou, C. Zhou, C. Zhu, Q. Zhu, G. Zou, H. Zou, Q. Zhang, C.-Y. Lu, C.-Z. Peng, X. Yuan, M. Gong, X. Zhu, and J.-W. Pan, One- and two-dimensional cluster states for topological phase simulation and measurement-based quantum computation, Nature Physics 22, 430 (2026).DOI
- [32]B. Pokharel and D. A. Lidar, Better-than-classical Grover search via quantum error detection and suppression, npj Quantum Information 10, 23 (2024).arxiv.org/abs/2211.04543
- [33]A. E. Roth and E. Peranson, The redesign of the matching market for American physicians: Some engineering aspects of economic design, American economic review 89, 748 (1999).pubmed.ncbi.nlm.nih.gov/29115787
- [34]National Resident Matching Program, NRMP releases results of the 2026 main residency match for more than 38,000 future residents, https://www.nrmp.org/about/news/2026/03/nrmp-releases-results-of-the-2026-main-residency-match-for-more-than-38000-future-residents/ (2026), published March 20, 2026.
- [35]See Supplemental Material at [URL will be inserted by publisher] for additional theoretical and experimental details, which includes Refs. [38–40].
- [36]C. M. Dawson and M. A. Nielsen, The Solovay-Kitaev algorithm, Quantum Information and Computation 6, 81 (2006), arXiv:quant-ph/0505030.DOI
- [37]J. Nie, W. Zi, and X. Sun, Quantum circuit for multi-qubit Toffoli gate with optimal resource (2024), arXiv:2402.05053 [quant-ph].arxiv.org/abs/2402.05053



