Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
arXiv:1001.3116 · doi:10.1007/s11128-010-0200-3
Abstract
In [Choi08], we introduced the notion of minor-embedding in adiabatic quantum optimization. A minor-embedding of a graph G in a quantum hardware graph U is a subgraph of U such that G can be obtained from it by contracting edges. In this paper, we describe the intertwined adiabatic quantum architecture design problem, which is to construct a hardware graph U that satisfies all known physical constraints and, at the same time, permits an efficient minor-embedding algorithm. We illustrate an optimal complete-graph-minor hardware graph. Given a family F of graphs, a (host) graph U is called F-minor-universal if for each graph G in F, U contains a minor-embedding of G. The problem for designing a F-minor-universal hardware graph U_{sparse} in which F consists of a family of sparse graphs (e.g., bounded degree graphs) is open.
10 pages, 5 figures
References in corpus (4)
Cited by in corpus (114)
- Noisy intermediate-scale quantum (NISQ) algorithms
- Quantum annealing with more than one hundred qubits
- Defining and detecting quantum speedup
- Quantum Annealing for Industry Applications: Introduction and Review
- Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
- Opportunities and challenges for quantum-assisted machine learning in near-term quantum computers
- Quantum Optimization of Fully-Connected Spin Glasses
- Error corrected quantum annealing with hundreds of qubits
- Efficient partition of integer optimization problems with one-hot encoding
- Open source software in quantum computing
- Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
- Probing for quantum speedup in spin glass problems with planted solutions
- Quantum annealing with a network of all-to-all connected, two-photon driven Kerr nonlinear oscillators
- Nonnegative/binary matrix factorization with a D-Wave quantum annealer
- Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
- A full-stack view of probabilistic computing with p-bits: devices, architectures and algorithms
- Consistency Tests of Classical and Quantum Models for a Quantum Annealer
- Quantum optimization with arbitrary connectivity using Rydberg atom arrays
- Fluctuation theorems for quantum processes
- Quantum-Assisted Learning of Hardware-Embedded Probabilistic Graphical Models
- Quantum Computation Based on Quantum Adiabatic Bifurcations of Kerr-Nonlinear Parametric Oscillators
- Robust quantum optimizer with full connectivity
- A NASA Perspective on Quantum Computing: Opportunities and Challenges
- Quantum Machine Learning: from physics to software engineering
- Quantum Annealing Correction with Minor Embedding
- Bayesian Network Structure Learning Using Quantum Annealing
- Domain wall encoding of discrete variables for quantum annealing and QAOA
- Leveraging Quantum Annealing for Large MIMO Processing in Centralized Radio Access Networks
- A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
- A cross-disciplinary introduction to quantum annealing-based algorithms
- Weighted p-bits for FPGA implementation of probabilistic circuits
- Autonomous Probabilistic Coprocessing with Petaflips per Second
- Temperature scaling law for quantum annealing optimizers
- MAX 2-SAT with up to 108 qubits
- A Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera Graph
- Improving quantum annealing of the ferromagnetic -spin model through pausing
- 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
- Nested Quantum Annealing Correction
- Building an iterative heuristic solver for a quantum annealer
- Stabilisers as a design tool for new forms of Lechner-Hauke-Zoller Annealer
- Readiness of Quantum Optimization Machines for Industrial Applications
- Enhancing Quantum Annealing Performance for the Molecular Similarity Problem
- Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
- Hybrid quantum annealing for larger-than-QPU lattice-structured problems
- Thermalization, freeze-out and noise: deciphering experimental quantum annealers
- Two-photon driven Kerr resonator for quantum annealing with three-dimensional circuit QED
- An energetic perspective on rapid quenches in quantum annealing
- A quantum-walk-inspired adiabatic algorithm for graph isomorphism
- Charged particle tracking with quantum annealing-inspired optimization
- Variational optimization of the quantum annealing schedule for the Lechner-Hauke-Zoller scheme
- Improved Boltzmann machines with error corrected quantum annealing
- Boosting quantum annealer performance via sample persistence
- Simulated Quantum Annealing with Two All-to-All Connectivity Schemes
- Quantum-assisted associative adversarial network: Applying quantum annealing in deep learning
- An Integrated Programming and Development Environment for Adiabatic Quantum Optimization
- Scalable effective temperature reduction for quantum annealers via nested quantum annealing correction
- Understanding domain-wall encoding theoretically and experimentally
- Quantum adiabatic machine learning with zooming
- A family of [[6k, 2k, 2]] codes for practical, scalable adiabatic quantum computation
- Testing a quantum annealer as a quantum thermal sampler
- Guiding Principle for Minor-Embedding in Simulated-Annealing-Based Ising Machines
- Transforming Generalized Ising Model into Boltzmann Machine
- Improving performance of logical qubits by parameter tuning and topology compensation
- Embedding of Complete Graphs in Broken Chimera Graphs
- Perils of Embedding for Sampling Problems
- Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete
- Fair sampling of ground-state configurations of binary optimization problems
- A Quantum N-Queens Solver
- Estimating the Density of States of Frustrated Spin Systems
- Minimal Constraints in the Parity Formulation of Optimization Problems
- Annealing-Assisted Column Generation for Inequality-Constrained Combinatorial Optimization Problems
- A Hybrid Quantum-Classical Paradigm to Mitigate Embedding Costs in Quantum Annealing
- Disorder-assisted graph coloring on quantum annealers
- Quantum annealing with twisted fields
- Scalable Connectivity for Ising Machines: Dense to Sparse
- Performance enhancement of quantum annealing under the Lechner-Hauke-Zoller scheme by non-linear driving of the constraint term
- 4-clique Network Minor Embedding for Quantum Annealers
- Quantum Vertex Model for Reversible Classical Computing
- Localization transition induced by programmable disorder
- Optimization of Image Acquisition for Earth Observation Satellites via Quantum Computing
- Quantum annealing speedup of embedded problems via suppression of Griffiths singularities
- Enhancing the efficiency of quantum annealing via reinforcement: A path-integral Monte Carlo simulation of the quantum reinforcement algorithm
- Nonvolatile bistable memory and Ising machine based on Micro-Electro-Mechanical Systems
- Post-processing variationally scheduled quantum algorithm for constrained combinatorial optimization problems
- Dynamical process of a bit-width reduced Ising model with simulated annealing
- Demonstration of long-range correlations via susceptibility measurements in a one-dimensional superconducting Josephson spin chain
- Quantum Annealing Machines Based on Semiconductor Nanostructures
- Quantum walk on a chimera graph
- Performance Models for Split-execution Computing Systems
- Annealing for prediction of grand canonical crystal structures: Efficient implementation of n-body atomic interactions
- Solving Spin Glasses with Optimized Trees of Clustered Spins
- Improving the efficiency of quantum annealing with controlled diagonal catalysts
- Using copies to improve precision in continuous-time quantum computing
- Impact of Fixing Spins in a Quantum Annealer with Energy Rescaling
- Utility of NISQ devices: optimizing experimental parameters for the fabrication of Au atomic junction using gate-based quantum computers
- Linearizing Binary Optimization Problems Using Variable Posets for Ising Machines
- Analysis of the Hopfield Model with Discrete Coupling
- Quadratic constrained mixed discrete optimization with an adiabatic quantum optimizer
- Development of research network on Quantum Annealing Computation and Information using Google Scholar data
- Performance of Domain-Wall Encoding for Quantum Annealing
- A scalable 2-local architecture for quantum annealing of Ising models with arbitrary dimensions
- Optimal Sufficient Requirements on the Embedded Ising Problem in Polynomial Time
- Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking
- Comparing Quantum Annealing and Spiking Neuromorphic Computing for Sampling Binary Sparse Coding QUBO Problems
- Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming
- Minor embedding with Stuart-Landau oscillator networks
- Transfer Learning for Deep-Unfolded Combinatorial Optimization Solver with Quantum Annealer
- Generation of all-to-all connections in a two-dimensional qubit array with two-body interactions
- Practical hybrid decoding scheme for parity-encoded spin systems
- Quantum annealing and condensed matter physics
- Improving success probability in the LHZ parity embedding by computing with quantum walks
- Steady state distributions of network of degenerate optical parametric oscillators in solving combinatorial optimization problems
- Formulation and evaluation of ocean dynamics problems as optimization problems for quantum annealing machines
- Frustration-enhanced quantum annealing correction models with additional inter-replica interactions