%0 DATA
%A PW, Mills
%A Russell, Rundle
%A John, Samson
%A Simon J, Devitt
%A Todd, Tilma
%A Vincent, Dwyer
%A Mark, Everitt
%D 2019
%T Quantum invariants and the graph isomorphism problem
%U https://repository.lboro.ac.uk/articles/journal_contribution/Quantum_invariants_and_the_graph_isomorphism_problem/11316398
%2 https://repository.lboro.ac.uk/ndownloader/files/20065349
%K Uncategorised value
%X 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.