A Quantum Walk Across Biological Networks: A Demonstration on a 40-Qubit Superconducting Processor

Abstract

A joint team from Algorithmiq and IBM Quantum has run a discrete-time quantum walk (DTQW) on complex networks drawn from protein-protein interaction (PPI) data, using 40 qubits of real quantum hardware. Rather than accept the extreme circuit depth demanded by conventional dense encodings, the researchers traded depth for qubit count, pairing a symmetry-sector encoding with postselection. On a benchmark graph this cut the depth of a single walk step by roughly two orders of magnitude. Applied to an asthma-associated gene network, the walk lifted FLVCR1, a gene placed well down the list by classical benchmark methods, to fourth position. The authors attribute the shift to quantum interference and present the case as a proof of principle for network medicine. [Quantum Biology Society] In network medicine, where disease mechanisms are read off the interaction networks that link proteins and genes, the classical random walk has long been a workhorse. A walker hops between nodes at random, and the resulting visit frequencies serve as a measure of importance. Adding the quantum principles of superposition and interference produces a quantum walk, whose probability spreads through a graph in a way that has no classical counterpart, and researchers have looked to it as a route to a different kind of network analysis. Computing such a walk on a real biological network has been another matter. Biological graphs are heterogeneous, with node degrees that vary from one vertex to the next, and running a quantum walk over that kind of irregular structure on today's noisy, pre-fault-tolerant hardware has been close to out of reach. A paper published online in npj Quantum Information on 24 July 2026, currently available as an accepted but not yet copyedited Article in Press, reports an experiment that pushes past this barrier. Working on IBM Heron superconducting processors with 156 qubits, researchers at Algorithmiq and IBM Quantum used up to 40 qubits to drive a discrete-time quantum walk through seven steps on a graph of 17 nodes and 20 edges. The authors describe it as the largest DTQW implementation on complex graphs on superconducting hardware to date. ■ Circuit Depth as the Bottleneck, and a Symmetry-Sector Way Around It When qubits were scarce, the natural choice was dense encoding, which compresses N walker positions into log₂N qubits plus a coin qubit. The saving comes at a price. Dense encoding leans on multi-controlled gates whose cost climbs steeply, and circuit depth climbs with it. The paper puts a number on this: with the state-of-the-art design of Sato and Saito, a single walk step on an 8-node, 8-edge graph decomposes into 1,218 entangling layers under idealized all-to-all connectivity, and 2,882 once the heavy-hex connectivity of IBM's processors is imposed. At that depth, decoherence dismantles the computation before it can finish. The researchers took the opposite approach. Symmetry-sector encoding: they allocated twice as many qubits as the graph has edges, 2|E| in all, and confined the state to the single-excitation subspace, in which exactly one qubit sits in the excited state |1>. Among 40 qubits, the single qubit that is switched on encodes both where the walker is and which way it is about to hop. Since qubits tend to decay from |1> toward |0>, states of higher Hamming weight are less stable over time, which is part of the authors' reasoning for choosing weight 1. Postselection as noise mitigation: any measurement that returns two or more excitations, or none at all, has violated the single-excitation symmetry and is discarded as a detected error. A further optimization rotates the computational basis into domain-wall states before the coin operator is applied and rotates it back afterwards, which approximately halves both the number of two-qubit native entangling gates and the transpiled depth of that block. The larger share of the depth reduction, however, comes from the fact that the coin and shift operators act in parallel across the qubit register, so their depth does not grow with the number of nodes or edges but with the maximum node degree. On the same 8-node benchmark, one step of the new framework needs 11 entangling layers under all-to-all connectivity and 28 under heavy-hex, roughly a hundredfold reduction against the reference design. ■ Seven Steps on 40 Qubits, and the Hellinger Fidelity That Held The experiments used three subgraphs extracted from BioPlex 3.0, a proteome-scale map of the human interactome: 11 nodes and 12 edges on 24 qubits, 15 nodes and 18 edges on 36 qubits, and 17 nodes and 20 edges on 40 qubits. The 24- and 40-qubit circuits ran on ibm_kingston, a Heron R2 device, and the 36-qubit circuit on ibm_pittsburgh, a Heron R3 device. Without postselection, the measured distributions matched theory poorly from the outset. At the first step, Hellinger fidelity stood at 0.79, 0.61 and 0.57 for the three graphs, which the authors read as evidence that the encoding alone cannot preserve coherence. With postselection applied, the picture changed. Fidelity stayed above 0.95, 0.90 and 0.87 respectively across all seven steps, including for the largest circuit, which reached 287 entangling layers on 40 qubits by step 7. Because a noisy circuit gradually drifts toward a featureless baseline distribution, a high Hellinger fidelity can flatter a result. The authors therefore also report a baseline-corrected fidelity, measured against the stationary distribution in which probability is spread evenly over directed-edge states and so falls on each node in proportion to its degree. That corrected figure remained at or above 0.71, 0.46 and 0.54 for the three graphs, which the authors take as an indication that the postselected results carry genuine signal rather than noise-driven flattening. ■ A Proof of Principle in Asthma Gene Prioritization The team then applied the measured walk dynamics to a disease-gene discovery task. HLA-DQA1, node 7 in the 11-node graph and one of the most strongly asthma-associated genes by genome-wide association study p-value, was chosen as the starting point for the walker, and the 24-qubit experiment was extended to nine steps. At each step the quantum probability at each node was compared with the corresponding classical random-walk probability, and the difference, normalized by the collision probability of the quantum distribution, gave a quantum interference index. Each node's score was its maximum index over time. HLA-C, PON2 and HLA-G took the top three places, all of them close to the seed and visited early in the walk. The result that drew attention was FLVCR1, described in the paper as the choline and heme transporter 1, which came fourth despite having no direct edge to the seed node or its neighbours and being ranked seventh by PageRank and ninth by DIAMOnD. The authors attribute its prioritization to amplitude interference rather than simple topological closeness, and note that FLVCR1 meets the GWAS significance threshold and has been associated with asthma across age groups, having been reported as a risk factor for childhood-onset disease. The partial overlap with the classical rankings, they argue, shows consistency with established methods, while the differences point to information a quantum walk might supply that classical approaches miss. ■ Significance and Limits Running a large quantum walk on the irregular, heterogeneous graphs characteristic of biological data, rather than on the regular lattices and cycle graphs used in earlier demonstrations, is the central achievement here, and it was done on real superconducting hardware rather than in simulation. The authors are explicit about the boundaries of the claim. The asthma case study runs on an 11-node subgraph chosen to fit current hardware limits, which restricts direct real-world applicability and leaves the work at the proof-of-concept stage. All three test graphs share a maximum node degree of 3, and it is that maximum degree, rather than graph size, that governs how the circuit depth scales. The cost of postselection also grows sharply: the fraction of retained bitstrings decays exponentially with depth, and in the 40-qubit run only about 0.2 per cent survived at step 7, roughly 17,000 out of nearly nine million shots. Some errors escape the symmetry check altogether, including phase flips and paired bit flips that leave the excitation count unchanged; the authors estimate the rate of such undetectable gate errors at around 3 × 10⁻⁴. They add that a walk run without postselection would need gate errors of order 10⁻⁴ to reach the same success probability they obtained with it, against the roughly 10⁻³ two-qubit gate errors available today, and suggest that deeper circuits will call for more advanced mitigation, such as tensor-network error mitigation adapted to work alongside postselection. Set against hardware roadmaps that point toward physical qubit counts in the millions, the authors make the case that trading circuit depth for qubits is a more tractable path forward than pushing gate fidelities alone, and one that should let the same framework reach larger and denser biological networks as the hardware improves. #QuantumWalk #DiscreteTimeQuantumWalk #QuantumComputing #ProteinInteractionNetwork #PPINetwork #DiseaseGenePrioritization #NetworkMedicine #IBMQuantum #ErrorMitigation #Postselection #Asthma #npjQuantumInformation #OpenAccess #QuantumBiologySociety Source: https://www.nature.com/articles/s41534-026-01332-w Circuit design code: https://doi.org/10.6084/m9.figshare.32218227