Quantum invariants and the graph isomorphism problem
| Autor: | P. W. Mills, Todd Tilma, Mark J. Everitt, Simon J. Devitt, John Samson, Russell P. Rundle, Vincent M. Dwyer |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
Physics
Discrete mathematics Strongly regular graph Quantum Physics FOS: Physical sciences 0102 computer and information sciences 01 natural sciences Graph 010201 computation theory & mathematics Qubit Quantum graph Graph isomorphism problem 0103 physical sciences Invariant (mathematics) 010306 general physics Quantum Physics (quant-ph) Quantum Polynomial number MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Physical Review A. 100(No. 5) |
| ISSN: | 2469-9926 |
| Popis: | Three new graph invariants are introduced which may be measured from a quantum graph state and form examples of a framework under which other graph invariants can be constructed. Each invariant is based on distinguishing a different number of qubits. This is done by applying alternate measurements to the qubits to be distinguished. The performance of these invariants is evaluated and compared to classical invariants. We verify that the invariants can distinguish all non-isomorphic graphs with 9 or fewer nodes. The invariants have also been applied to `classically hard' strongly regular graphs, successfully distinguishing all strongly regular graphs of up to 29 nodes, and preliminarily to weighted graphs. We have found that although it is possible to prepare states with a polynomial number of operations, the average number of preparations required to distinguish non-isomorphic graph states scales exponentially with the number of nodes. We have so far been unable to find operators which reliably compare graphs and reduce the required number of preparations to feasible levels. Comprehensive update including a study of scalability of algorithms. 12 pages, 7 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|