Optimal sufficient requirements on the embedded Ising problem in polynomial time

One of the central applications for quantum annealers is to find the solutions of Ising problems. Suitable Ising problems, however, need to be formulated such that they, on the one hand, respect the specific restrictions of the hardware and, on the other hand, represent the original problems which s...

Full description

Saved in:
Bibliographic Details
Published in:Quantum information processing 2023-08, Vol.22 (8), Article 305
Main Authors: Lobe, Elisabeth, Kaibel, Volker
Format: Article
Language:English
Subjects:
Data Structures and Information Theory
Mathematical Physics
Physics
Physics and Astronomy
Quantum Computing
Quantum Information Technology
Quantum Physics
Spintronics
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:One of the central applications for quantum annealers is to find the solutions of Ising problems. Suitable Ising problems, however, need to be formulated such that they, on the one hand, respect the specific restrictions of the hardware and, on the other hand, represent the original problems which shall actually be solved. We evaluate sufficient requirements on such an embedded Ising problem analytically and transform them into a linear optimization problem. With an objective function aiming to minimize the maximal absolute problem parameter, the precision issues of the annealers are addressed. Due to the redundancy of several constraints, we can show that the formally exponentially large optimization problem can be reduced and finally solved in polynomial time for the standard embedding setting where the embedded vertices induce trees. This allows to formulate provably equivalent embedded Ising problems in a practical setup.
ISSN:1573-1332
1573-1332
DOI:10.1007/s11128-023-04058-2