A Constant Measurement Quantum Algorithm for Graph Connectivity
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912142991556608 |
|---|---|
| author | Mansky, Maximilian Balthasar Kam, Chonfai Linnhoff-Popien, Claudia |
| author_facet | Mansky, Maximilian Balthasar Kam, Chonfai Linnhoff-Popien, Claudia |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_15015 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Constant Measurement Quantum Algorithm for Graph Connectivity Mansky, Maximilian Balthasar Kam, Chonfai Linnhoff-Popien, Claudia Quantum Physics 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. |
| title | A Constant Measurement Quantum Algorithm for Graph Connectivity |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2411.15015 |