Quantum invariants and the graph isomorphism problem
PW Mills
Russell Rundle
John Samson
Simon J Devitt
Todd Tilma
Vincent Dwyer
Mark Everitt
2134/11316398.v1
https://repository.lboro.ac.uk/articles/Quantum_invariants_and_the_graph_isomorphism_problem/11316398
Three 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 different 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 nonisomorphic graphs with nine 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 nonisomorphic
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.
2019-12-06 11:24:32
Uncategorised value