Fast graph operations in quantum computation
arXiv:1510.03742 · doi:10.1103/PhysRevA.93.032314
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.
arXiv comment9 pages, 1 figure. Comments welcome
References in corpus (24)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Mechanics helps in searching for a needle in a haystack
- Quantum algorithm for solving linear systems of equations
- Measurement-based quantum computation with cluster states
- Improved Simulation of Stabilizer Circuits
- Measurement-based quantum computation
- Multi-party entanglement in graph states
- Efficient high-fidelity quantum computation using matter qubits and linear optics
- Quantum State Discrimination
- Graphical description of the action of local Clifford transformations on graph states
- Architectures for a quantum random access memory
- Efficient quantum computation with probabilistic quantum gates
- Brokered Graph State Quantum Computing
- An efficient algorithm to recognize local Clifford equivalence of graph states
- Local unitary versus local Clifford equivalence of stabilizer states
- Fully fault tolerant quantum computation with non-deterministic gates
- 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
- Efficient Graph State Construction Under the Barrett and Kok Scheme
- Probabilistic growth of large entangled states with low error accumulation
- 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