Correspondence Between QUBO, HOBO, Ising Formulation, and Quantum Circuits in Quantum Annealing

Correspondence Between QUBO, HOBO, Ising Formulation, and Quantum Circuits in Quantum Annealing

Introduction

Quantum computers have the potential to radically transform our lives. However, the mechanisms and applications can often be complex and difficult to understand. In this article, we will gradually explain how mathematical models such as QUBO and HOBO are transformed into the Ising model and then introduced into quantum circuits.

This article is based on questions raised in a lecture for high school students at a quantum seminar. I decided to share it on this blog because others might also have similar doubts.

What are QUBO and HOBO?

QUBO (Quadratic Unconstrained Binary Optimization) and HOBO (Higher-Order Binary Optimization) are mathematical frameworks for solving combinatorial optimization problems. These models optimize an objective function using binary (0 and 1) variables.

• QUBO: An optimization problem that includes terms up to the second degree. For example, f(x) = x_1x_2 + x_2x_3 + \dots, where products of variables are present.
• HOBO: An optimization problem that includes higher-order terms (third degree and above).

These models can be applied to many real-world problems, such as scheduling, graph coloring, and pattern recognition.

Converting QUBO/HOBO to the Ising Model

The Ising model is used in physics to represent the interaction of spins in magnetic materials. By converting QUBO or HOBO into the Ising model, we can perform quantum computations using quantum circuits.

Steps of Conversion:

1. Variable Conversion:

   • In QUBO and HOBO, variables are 0 or 1, while in the Ising model, spins take values of +1 or -1.

   • Example of variable conversion:

     x_i = \frac{1 - z_i}{2}

     Here, x_i is a QUBO/HOBO variable, and z_i is a spin variable in the Ising model. The goal is to map x=0to z=1 and x=1 to z=-1. In quantum circuits, the expectation value ofz is 1 when in the |0\rangle state and -1 in the |1\rangle state. Hence, the above transformation is appropriate.

2. Reconstructing the Objective Function:

   • After converting the variables, reconstruct the objective function to fit the Ising model.
   • This allows us to express the problem as an Ising Hamiltonian.

Eliminating Constants

The transformed Ising Hamiltonian may contain constant terms. In quantum computation, these constants serve as energy baselines and do not affect the results. Therefore, removing constant terms simplifies the computation.

Example:

Here, C is a constant. In quantum computations, we can ignore this constant, simplifying the Hamiltonian to:

Introducing Hamiltonian Coefficients as Rotation Angles in Time Evolution Operators

In quantum circuits, the Hamiltonian is used to evolve the state of qubits over time. Specifically, the coefficients of the Hamiltonian are introduced as rotation angles in quantum gates.

Steps:

1. Decomposing the Hamiltonian:

   • Decompose the Hamiltonian H into Pauli matrices:

     H = \sum_k \theta_k P_k

     Here, \theta_k are the coefficients, and P_k are the basis operators.

2. Correspondence with Quantum Gates:

   • Each basis operator P_k corresponds to a quantum gate (such as rotation gates).
   • The coefficients \theta_k are used as rotation angles for the gates.

3. Constructing the Time Evolution Operator:

   • Combine all the gates to express the time evolution under the Hamiltonian:

     U(t) = e^{-iHt/\hbar}

   • This allows the qubits’ state to evolve according to the Hamiltonian.

Time Evolution Operators and Arbitrary Rotation Gates

The Hamiltonians described above are transformed into gates like RZ and RZZ gates in time evolution, often called "arbitrary rotation gates." These gates allow for specifying the rotation angle, using the coefficients from the Hamiltonian.

For further details, you can explore techniques such as Trotter decomposition, but for now, we’ll focus on introducing the Hamiltonian into quantum gates.

Reference:
https://blueqat.com/yuichiro_minato2/8125332c-8b29-4a9d-ab94-0f9c74aad75f

In quantum circuits, this is converted to a form like RZ(-2at) or RZ(2at), where (a) corresponds to the coefficient in the Hamiltonian. This rule allows us to go from QUBO/HOBO to the Ising Hamiltonian, and then introduce the coefficients as rotation angles in the time evolution operator (RZ, RZZ gates in this case).

Example Problem

Let's explore a concrete example using Python.

For instance, let's consider the following QUBO problem:

In this equation, (x) takes values of 0 or 1. With two qubits, the minimum value will likely occur at 00 or 01 since (x_0 = 1) would increase the cost.

import sympy as sp

# Define variables
x0, x1 = sp.symbols('x0 x1')

# Create the expression
expr = 2*x0 + 3*x0*x1

# Display the expression
expr

Next, we convert the expression to (z) variables.

z0, z1 = sp.symbols('z0 z1')
expr_substituted = expr.subs({x0:(1 - z0)/2, x1:(1 - z1)/2})
expr_substituted.expand()

This results in:

Since the constant term does not affect the result, we ignore it and obtain:

Next, we examine the coefficients. The coefficient for (z_0z_1) is (3/4), which corresponds to the RZZ gate with a rotation angle of RZZ(-23/4t). Similarly, the coefficient (-7/4) for (z_0) corresponds to RZ(27/4t), and (-3/4) for (z_1) corresponds to RZ(23/4t).

Now, let's use Qiskit.

! pip install qiskit qiskit-optimization pylatexenc

from qiskit import QuantumCircuit, transpile
from qiskit.primitives import Sampler
from qiskit_algorithms.optimizers import COBYLA
from qiskit.quantum_info import SparsePauliOp
from qiskit_algorithms.minimum_eigensolvers import QAOA

initial_state_circuit = QuantumCircuit(2)
initial_state_circuit.h(0)
initial_state_circuit.h(1)
initial_state_circuit.barrier()

sampler = Sampler()
optimizer = COBYLA()
step = 1

# Define cost Hamiltonian
cost = SparsePauliOp(["ZZ", "ZI", "IZ"], [3/4, -7/4, -3/4])

qaoa = QAOA(
    sampler,
    optimizer,
    reps=step,
    initial_state=initial_state_circuit,
)
result = qaoa.compute_minimum_eigenvalue(cost)
print(result)
display(result.optimal_circuit.draw('mpl'))

Summary

By understanding the steps from formulating QUBO or HOBO to converting to the Ising model, eliminating constants, and implementing them in quantum circuits, we can grasp the basic mechanics of quantum computing. Introducing relatable examples and visual aids will help make these concepts more accessible, even for high school students.