2-Step QAOA: A New Approach to Preparing Quantum States for the XY Mixer

2-Step QAOA: A New Approach to Preparing Quantum States for the XY Mixer

In the field of quantum computing, new techniques are continually being developed to improve the efficiency and effectiveness of quantum algorithms. Recently, a technique called 2-Step QAOA (Quantum Approximate Optimization Algorithm) was introduced. This method provides a novel approach to easily creating quantum states that are suitable for use with the XY mixer.

Two-Step QAOA: Enhancing Quantum Optimization by Decomposing One-Hot Constraints in QUBO Formulations
Yuichiro Minato

The Quantum Approximate Optimization Algorithm (QAOA) has shown promise in solving combinatorial optimization problems by leveraging quantum computational power. We propose a simple approach, the Two-Step QAOA, which aims to improve the effectiveness of QAOA by decomposing problems with one-hot encoding QUBO (Quadratic Unconstrained Binary Optimization) formulations. By identifying and separating the problem into two stages, we transform soft constraints into hard constraints, simplifying the generation of initial conditions and enabling more efficient optimization. The method is particularly beneficial for tackling complex societal problems that often involve intricate constraint structures.

https://arxiv.org/abs/2408.05383

What is 2-Step QAOA?

2-Step QAOA is a technique that creates quantum states compatible with the XY mixer by consecutively executing two different types of QAOA. The XY mixer plays a crucial role in certain quantum algorithms, requiring a specific form of quantum state to function effectively. Typically, this state must be a Dicke state.

Challenges of Dicke States

A Dicke state is a quantum state where a certain number of qubits are in the "1" state, while the remaining qubits are in the "0" state. For the XY mixer to work effectively, this Dicke state must be prepared in a specific form, a process that is complex and resource-intensive.

Traditionally, creating this state required precise and intricate procedures. However, 2-Step QAOA offers a promising solution to this challenge.

The Theory Behind 2-Step QAOA

In 2-Step QAOA, the first QAOA uses constraints to create the quantum state. In the second QAOA, those constraints are removed, and the computation begins using the quantum state created by the first QAOA. QAOA is based on quantum annealing, and by using the ground state obtained from the first QAOA, the computation proceeds with the XY mixer to reach the ground state of another problem to be solved.

This approach simplifies the computation steps, making the process of preparing quantum states easier while leaving room for further optimization.

Advantages and Applications

The primary advantage of 2-Step QAOA lies in its ability to make the XY mixer more accessible. By reducing the complexity of preparing the initial state, the implementation of algorithms requiring the XY mixer becomes easier.

Moreover, this method opens up new possibilities for optimization, enabling more efficient quantum computation. The step-by-step process is easy to understand and will be a valuable tool for those exploring or experimenting with quantum algorithms.

How to Use It

This algorithm can be easily implemented using standard tools like IBM's Qiskit. No special tools are required, and existing tools can be adapted to create the algorithm.

Example

In this example, we'll set up a problem with three qubits, where only one is selected. First, we'll prepare a QUBO (Quadratic Unconstrained Binary Optimization) formulation and then convert it into a format that can be solved with quantum circuits, known as Ising.

We define the variables in QUBO as (x_0, x_1, x_2), and the qubits as (q_0, q_1, q_2). The variables (x) take binary values 0 and 1, while the qubits (q) take values +1 and -1. We assign a weight of 10 to (q_1) to encourage its selection. This requires both constraints and a cost function.

This example is adapted from the following article:

Playing with Qiskit (20) — QAOA with Qiskit Optimization
https://zenn.dev/derwind/articles/dwd-qiskit20

We'll start with the constraint condition (which will later be converted to (q)):

Condition for selecting (q_1):

Let's begin by creating the initial state. We'll use 2-Step QAOA to create an initial state using an H gate for superposition, followed by a mixer with X gates, and then apply the constraint condition in QAOA.

Let's implement this in Qiskit:

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

Load the tools and prepare the initial state:

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

display(initial_state_circuit.draw('mpl'))

Next, we'll convert the constraint condition into QAOA. We'll manually input the formula using sympy. Let's convert the variable (x) into (q) (Z in Hamiltonian).

To match the values in QUBO, where (x=0) corresponds to (z=-1) and (x=1) to (z=1), we'll substitute (-z = 2x - 1).

import sympy as sp

# Define variables
x0, x1, x2, z0, z1, z2 = sp.symbols('x0 x1 x2 z0 z1 z2')

# Define expression
expression = (x0 + x1 + x2 - 1)**2

# Expand
expanded_expression = sp.expand(expression)

print(expanded_expression)

# Replace x^2 with x
substituted_expression = expanded_expression.subs({x0**2: x0, x1**2: x1, x2**2: x2})

print(substituted_expression)

# Substitute -z = 2x - 1
final_expression = substituted_expression.subs({x0: (-z0 + 1)/2, x1: (-z1 + 1)/2, x2: (-z2 + 1)/2})

# Expand again
expanded_final_expression = sp.expand(final_expression)

# Convert fractions to decimals
decimal_expression = sp.N(expanded_final_expression)

# Display the result
print(decimal_expression)

The result is:

0.5*z0*z1 + 0.5*z0*z2 - 0.5*z0 + 0.5*z1*z2 - 0.5*z1 - 0.5*z2 + 1.0

We'll implement this manually into QAOA, excluding the constant 1.0.

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

# Define the cost Hamiltonian
cost = SparsePauliOp(["ZZI", "ZIZ", "IZZ", "ZII", "IZI", "IIZ"], [0.5, 0.5, 0.5, -0.5, -0.5, -0.5])

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'))

The result is:

{   'aux_operators_evaluated': None,
    'best_measurement': {   'bitstring': '001',
                            'probability': 0.1361159839185406,
                            'state': 1,
                            'value': (-1+0j)},
    'cost_function_evals': 125,
    'eigenstate': {0: 0.028108483960627, 1: 0.111539508728194, 2: 0.111539508728194, 3: 0.186950878581939, 4: 0.111539508728194, 5: 0.186950878581939, 6: 0.186950878581939, 7: 0.076420354108974},
    'eigenvalue': -0.10535746385765882,
    'optimal_circuit': <qiskit.circuit.quantumcircuit.QuantumCircuit object at 0x7f34b9faab60>,
    'optimal_parameters': {   ParameterVectorElement(β[0]): 4.53294686272706,
                              ParameterVectorElement(γ[0]): 2.6926550359765855},
    'optimal_point': array([4.53294686, 2.692

65504]),
    'optimal_value': -0.10535746385765882,
    'optimizer_evals': None,
    'optimizer_result': <qiskit_algorithms.optimizers.optimizer.OptimizerResult object at 0x7f34b99d5de0>,
    'optimizer_time': 2.2393693923950195}

Now let's examine the circuit:

We can execute the QAOA with the obtained circuit and parameters by using assign_parameters.

from qiskit_aer import AerSimulator

bound_circuit = result.optimal_circuit.assign_parameters(result.optimal_parameters)

sim = AerSimulator()
t_qc = transpile(bound_circuit, backend=sim)
counts = sim.run(t_qc).result().get_counts()
print(counts)

The result is:

{'101': 67, '111': 12, '011': 62, '110': 59, '000': 68, '010': 237, '100': 248, '001': 271}

We've made some progress. Although it's not a perfect Dicke state, it seems achievable with further iterations.

Next, we'll use the created state as the initial state and execute QAOA again.

The cost Hamiltonian will be (H_{c_2} = 10Z_1).
We'll use the XY mixer this time.

Before that, we need to make some adjustments in Qiskit.

The previously generated quantum circuit includes measurement. We want to reuse the circuit but remove the measurement, so we'll copy the gates to a new circuit.

# Create a new circuit without measurements
new_circuit = QuantumCircuit(bound_circuit.num_qubits)

# Add non-measurement instructions to the new circuit
for instr, qargs, cargs in bound_circuit.data:
    if instr.name != "measure":
        new_circuit.append(instr, qargs, cargs)

# Replace the original circuit
bound_circuit = new_circuit
display(new_circuit.draw('mpl'))

Now let's proceed with the calculation.
We'll prepare the XY mixer. Each qubit is connected to all others, and the cost is applied only to the middle qubit (q_1).

mixer = SparsePauliOp(["XXI", "YYI", "XIX", "YIY", "IXX", "IYY"], [1/2, 1/2, 1/2, 1/2, 1/2, 1/2])
cost2 = SparsePauliOp(["IZI"], [10])

qaoa = QAOA(
    sampler,
    optimizer,
    reps=step,
    initial_state=new_circuit,
    mixer=mixer,
)
result2 = qaoa.compute_minimum_eigenvalue(cost2)
print(result2)

The result is:

{   'aux_operators_evaluated': None,
    'best_measurement': {   'bitstring': '010',
                            'probability': 0.6757586580378196,
                            'state': 2,
                            'value': (-10+0j)},
    'cost_function_evals': 176,
    'eigenstate': {0: 0.082178953352383, 1: 0.001601155937579, 2: 0.658789569931377, 3: 0.092518227299222, 4: 0.059313662657643, 5: 0.02451717463238, 6: 0.06924094024338, 7: 0.011840315946037},
    'eigenvalue': -6.647781068400323,
    'optimal_circuit': <qiskit.circuit.quantumcircuit.QuantumCircuit object at 0x7f34a3544670>,
    'optimal_parameters': {   ParameterVectorElement(β[0]): 5.7265622989569795,
                              ParameterVectorElement(γ[0]): -4.6198069088868525},
    'optimal_point': array([ 5.7265623 , -4.61980691]),
    'optimal_value': -6.647781068400323,
    'optimizer_evals': None,
    'optimizer_result': <qiskit_algorithms.optimizers.optimizer.OptimizerResult object at 0x7f34a1d31090>,
    'optimizer_time': 6.24747109413147}

It successfully outputs 010. Let's execute the state vector again.

bound_circuit2 = result2.optimal_circuit.assign_parameters(result2.optimal_parameters)

t_qc2 = transpile(bound_circuit2, backend=sim)
counts2 = sim.run(t_qc2).result().get_counts()
print(counts2)
display(bound_circuit2.draw('mpl'))

{'101': 23, '001': 2, '100': 64, '110': 71, '011': 80, '111': 15, '000': 83, '010': 686}

It was a great success.

Conclusion

The introduction of 2-Step QAOA marks significant progress in the field of quantum computing. By simplifying the preparation of quantum states compatible with the XY mixer, this technique has the potential to make advanced quantum algorithms more practical and accessible. As quantum computing continues to evolve, innovations like 2-Step QAOA will play a vital role in shaping the future of this exciting field.

In this blog, we have briefly introduced the potential of 2-Step QAOA. If you would like to learn more about the technical aspects and applications of this method, I encourage you to explore the latest research and developments in this field.