Dresden 2026 – scientific programme
Parts | Days | Selection | Search | Updates | Downloads | Help
QI: Fachverband Quanteninformation
QI 1: Quantum Computing and Algorithms I
QI 1.11: Talk
Monday, March 9, 2026, 12:30–12:45, BEY/0137
A Constant Measurement Quantum Algorithm for Graph Connectivity — •Maximilian Balthasar Mansky1, Chonfai Kam2, and Claudia Linnhoff-Popien1 — 1LMU Munich — 2Palermo University
We introduce a novel quantum algorithm for determining graph connectedness using a constant number of measurements. The algorithm can be extended to find connected components with a linear number of measurements. It relies on non-unitary abelian gates taken from ZX calculus. Due to the fusion rule, the two-qubit gates correspond to a large single action on the qubits. The algorithm is general and can handle any undirected graph, including those with repeated edges and self-loops. The depth of the algorithm is variable, depending on the graph, and we derive upper and lower bounds. The algorithm exhibits a state decay that can be remedied with ancilla qubits. We provide a numerical simulation of the algorithm.
Keywords: Quantum computing; Quantum algorithm; Graph connectedness