Speaker
Description
Using quantum annealing algorithms to solve optimization problems represents a promising path to achieving a practical quantum advantage in the NISQ era. Problems of interest are typically formulated as a quadratic unconstrained binary optimization (QUBO) and then encoded into a spin glass Hamiltonian with two-body spin interactions.
Recently the inclusion of higher-order terms into the formulation of optimization problems (PUBO's) has garnered much interest due to the promise of increased ressource effiency and potential speedups.
We study examples of relevant optimization problems that are naturally formulated as PUBO's and calculate the associated ressource savings when solving them using quantum annealing protocols with three-body spin interactions. Specifically we show that one can save up to an order of magnitude in for the encoding required logical qubits as compared to a QUBO formulation for certain problems like 3SAT.
We propose and discuss different approaches to engineer these higher-order interactions within a trapped ion quantum computer. These schemes are feasible to implement on current hardware and allow quantum annealing algorithms to solve larger optimization problems with relevance to industry.
