PhysRevA.100.052317.pdf (1.75 MB)
Quantum invariants and the graph isomorphism problem
journal contribution
posted on 2019-12-06, 11:24 authored by PW Mills, Russell Rundle, John Samson, Simon J Devitt, Todd Tilma, Vincent Dwyer, Mark EverittMark EverittThree 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.
Funding
Engineering and Physical Sciences Research Council Grant No. EP/N509516/1
Promotion of Science KAKENHI (C) Grant No. JP17K05569.
Australian Research Council Centre of Excellence in Engineered Quantum Systems EQUS Project No. CE110001013.
History
School
- Science
Department
- Physics
Published in
Physical Review AVolume
100Issue
5Publisher
American Physical Society (APS)Version
- VoR (Version of Record)
Publisher statement
This is an Open Access Article. It is published by American Physical Society under the Creative Commons Attribution 4.0 Unported Licence (CC BY). Full details of this licence are available at: http://creativecommons.org/licenses/by/4.0/Acceptance date
2019-05-16Publication date
2019-11-13ISSN
2469-9926eISSN
2469-9934Publisher version
Language
- en
Depositor
Dr Mark Everitt Deposit date: 4 December 2019Article number
052317Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC