Skip to main content
Kent Academic Repository

Fast graph operations in quantum computation

Zhao, Liming, Pérez-Delgado, Carlos A, Fitzsimons, Joseph F (2016) Fast graph operations in quantum computation. Physical Review A, 93 (3). Article Number 032314. ISSN 2469-9926. E-ISSN 2469-9934. (doi:10.1103/PhysRevA.93.032314) (KAR id:58072)


The connection between certain entangled states and graphs has been heavily studied in the context of measurement-based quantum computation as a tool for understanding entanglement. Here we show that this correspondence can be harnessed in the reverse direction to yield a graph data structure, which allows for more efficient manipulation and comparison of graphs than any possible classical structure. We introduce efficient algorithms for many transformation and comparison operations on graphs represented as graph states, and prove that no classical data structure can have similar performance for the full set of operations studied.

Item Type: Article
DOI/Identification number: 10.1103/PhysRevA.93.032314
Uncontrolled keywords: Quantum, Algorithms, Data Structures
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 75 Electronic computers. Computer science
Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Q Science > QC Physics > QC174.12 Quantum theory
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Carlos Perez Delgado
Date Deposited: 25 Oct 2016 14:07 UTC
Last Modified: 06 Dec 2022 11:54 UTC
Resource URI: (The current URI for this page, for reference purposes)

University of Kent Author Information

Pérez-Delgado, Carlos A.

Creator's ORCID:
CReDIT Contributor Roles:
  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.