Discriminating Non-Isomorphic Graphs with an Experimental Quantum Annealer
arXiv:2005.01241 · doi:10.1103/PhysRevA.102.032622
Abstract
We demonstrate experimentally the ability of a quantum annealer to distinguish between sets of non-isomorphic graphs that share the same classical Ising spectrum. Utilizing the pause-and-quench features recently introduced into D-Wave quantum annealing processors, which allow the user to probe the quantum Hamiltonian realized in the middle of an anneal, we show that obtaining thermal averages of diagonal observables of classically indistinguishable non-isomorphic graphs encoded into transverse-field Ising Hamiltonians enable their discrimination. We discuss the significance of our results in the context of the graph isomorphism problem.
9 pages, 4 figures
References in corpus (25)
- Quantum annealing with more than one hundred qubits
- Defining and detecting quantum speedup
- Quantum Boltzmann Machine
- Observation of topological phenomena in a programmable lattice of 1,800 qubits
- Experimental signature of programmable quantum annealing
- Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
- Graph Isomorphism in Quasipolynomial Time
- Reverse Quantum Annealing Approach to Portfolio Optimization Problems
- Experimental Demonstration of a Robust and Scalable Flux Qubit
- Probing for quantum speedup in spin glass problems with planted solutions
- Probing the Universality of Topological Defect Formation in a Quantum Annealer: Kibble-Zurek Mechanism and Beyond
- Consistency Tests of Classical and Quantum Models for a Quantum Annealer
- Power of Pausing: Advancing Understanding of Thermalization in Experimental Quantum Annealers
- Reverse annealing for the fully connected -spin model
- How "Quantum" is the D-Wave Machine?
- Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
- A deceptive step towards quantum speedup detection
- Exponential complexity of an adiabatic algorithm for an NP-complete problem
- Unraveling Quantum Annealers using Classical Hardness
- Improving quantum annealing of the ferromagnetic -spin model through pausing
- Graph isomorphism and adiabatic quantum computing
- Solving the Graph Isomorphism Problem with a Quantum Annealer
- Improved Boltzmann machines with error corrected quantum annealing
- The pitfalls of planar spin-glass benchmarks: Raising the bar for quantum annealers (again)
- Hearing the Shape of the Ising Model with a Programmable Superconducting-Flux Annealer