Diagrammatic approach to quantum search

Tad Hogg

Krišjānis Prūsis, Jevgēnijs Vihrovs, Thomas G Wong

Abstract In typical discrete-time quantum walk algorithms, one measures the position of the walker while ignoring its internal spin/coin state. Rather than neglecting the information in this internal state, we show that additionally measuring it doubles the success probability of many quantum spatial search algorithms. For example, this allows Grover's unstructured search problem to be solved with certainty, rather than with probability 1/2 if only the walker's position is measured, so the additional measurement yields a search algorithm that is twice as fast as without it, on average. Thus the internal state of discrete-time quantum walks holds valuable information that can be utilized to improve algorithms. Furthermore, we determine conditions for which spatial search problems on regular graphs are amenable to this doubling of the success probability, and this involves diagrammatically analyzing search using degenerate perturbation theory and deriving a useful formula for how the quantum walk acts in its reduced subspace.

A. Romanelli, A. Auyuanet, R. Donangelo

Naihong Hu, Ruining Li, Futao Wang

This paper investigates foundational quantum computing protocols from the intuitive perspective of categorical tensor-graph semantics within the category \textbf{FHilb}. While conventional Hilbert-space formalisms often conceal the structural nature of quantum algorithms behind high-dimensional matrix operations, the topological framework directly encodes algorithmic functionalities into their graphical skeletons. We provide a comprehensive topological reinterpretation of the Bernstein--Vazirani and Simon algorithms, demonstrating how topological transformations distill their core mathematical essence and clarify the operational mechanisms of oracles. Going beyond the standard qubit model, we construct explicit representations for the qutrit-adapted topological Deutsch--Jozsa and single-shot Grover algorithms. In particular, we establish a necessary and sufficient condition for the single-shot Grover search. We further implement CNOT gates via complementary Frobenius structures and investigate a diagrammatic decomposition scheme for the W-state preparation protocol. By bridging tensor category theory with practical quantum algorithmic design, this work furnishes a composable, scalable diagrammatic toolkit essential for automated circuit optimization across the evolving quantum hardware ecosystem.

Aleks Kissinger

In recent years, diagrammatic languages have been shown to be a powerful and expressive tool for reasoning about physical, logical, and semantic processes represented as morphisms in a monoidal category. In particular, categorical quantum mechanics, or "Quantum Picturalism", aims to turn concrete features of quantum theory into abstract structural properties, expressed in the form of diagrammatic identities. One way we search for these properties is to start with a concrete model (e.g. a set of linear maps or finite relations) and start composing generators into diagrams and looking for graphical identities. Naively, we could automate this procedure by enumerating all diagrams up to a given size and check for equalities, but this is intractable in practice because it produces far too many equations. Luckily, many of these identities are not primitive, but rather derivable from simpler ones. In 2010, Johansson, Dixon, and Bundy developed a technique called conjecture synthesis for automatically generating conjectured term equations to feed into an inductive theorem prover. In this extended abstract, we adapt this technique to diagrammatic theories, expressed as graph rewrite systems, and demonstrate its application by synthesising a graphical theory for studying entangled quantum states.

Lov K. Grover