Minor-embedding in adiabatic quantum computation. II: Minor-universal graph design

DOI10.1007/s11128-010-0200-3zbMath1216.81048arXiv1001.3116OpenAlexW3098146626MaRDI QIDQ544830

Vicky Choi

Publication date: 16 June 2011

Published in: Quantum Information Processing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1001.3116

zbMATH Keywords

graph minoradiabatic quantum computationuniversal graphadiabatic quantum architecture designminor-embedding

Mathematics Subject Classification ID

Quantum computation (81P68) Mathematical problems of computer architecture (68M07) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items

Fast clique minor generation in Chimera qubit connectivity graphs ⋮ A comparison of approaches for finding minimum identifying codes on graphs ⋮ Building an iterative heuristic solver for a quantum annealer ⋮ Differential geometric treewidth estimation in adiabatic quantum computation ⋮ Optimizing adiabatic quantum program compilation using a graph-theoretic framework ⋮ Modeling the Costas array problem in QUBO for quantum annealing ⋮ Template-Based Minor Embedding for Adiabatic Quantum Optimization ⋮ Boosting quantum annealer performance via sample persistence ⋮ Enhancing quantum annealing performance for the molecular similarity problem ⋮ Systematic and deterministic graph minor embedding for Cartesian products of graphs ⋮ Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets ⋮ An Updated Experimental Evaluation of Graph Bipartization Methods ⋮ Graph minors from simulated annealing for annealing machines with sparse connectivity ⋮ Optimal sufficient requirements on the embedded Ising problem in polynomial time ⋮ Minimizing minor embedding energy: an application in quantum annealing ⋮ Intersecting longest cycles in Archimedean tilings ⋮ Embedding of complete graphs in broken Chimera graphs ⋮ Minor embedding in broken chimera and derived graphs is NP-complete ⋮ Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results ⋮ QUBO formulation for the contact map overlap problem ⋮ Adiabatic quantum programming: minor embedding with hard faults ⋮ Simulated versus reduced noise quantum annealing in maximum independent set solution to wireless network scheduling ⋮ Efficiently embedding QUBO problems on adiabatic quantum computers ⋮ Quantum pattern recognition with multi-neuron interactions ⋮ A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing ⋮ Hard combinatorial problems and minor embeddings on lattice graphs

Cites Work

• Pseudo-Boolean optimization
• A partial k-arboretum of graphs with bounded treewidth
• Graph minors. XIII: The disjoint paths problem
• Colloquium: Quantum annealing and analog quantum computation
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation
• Simulating Quantum Computation by Contracting Tensor Networks
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Minor-embedding in adiabatic quantum computation. II: Minor-universal graph design