Dresden 2026 – wissenschaftliches Programm
Bereiche | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe
QI: Fachverband Quanteninformation
QI 1: Quantum Computing and Algorithms I
QI 1.11: Vortrag
Montag, 9. März 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