Fast graph operations in quantum computation

Abstract

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.

9 pages, 1 figure. Comments welcome

References in corpus (10)

• Quantum algorithm for solving linear systems of equations
• Multi-party entanglement in graph states
• Architectures for a quantum random access memory
• Brokered Graph State Quantum Computing
• Fault-Tolerant Topological One-Way Quantum Computation with Probabilistic Two-Qubit Gates
• Phase transition of computational power in the resource states for one-way quantum computation
• Optimal preparation of graph states
• Efficient construction of 2-D cluster states with probabilistic quantum gates
• Adaptive strategies for graph state growth in the presence of monitored errors
• Efficient growth of complex graph states via imperfect path erasure

Cited by in corpus (9)

• Information-theoretic bounds on quantum advantage in machine learning
• Schur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations
• Quantum assisted Gaussian process regression
• Machine learning \& artificial intelligence in the quantum domain
• What do QAOA energies reveal about graphs?
• Learning stabilizer states by Bell sampling
• On quantum invariants and the graph isomorphism problem
• Learning quantum graph states with product measurements
• Quantum algorithms for learning a hidden graph and beyond