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

什么是2-Step QAOA？

2-Step QAOA是一种通过连续执行两种不同的QAOA来创建与XY混合器兼容的量子态的技术。XY混合器在某些量子算法中起着至关重要的作用，需要特定形式的量子态才能有效工作。通常，这种状态必须是迪克态。

迪克态的挑战

迪克态是一种量子态，其中一定数量的量子比特处于“1”状态，而剩余的量子比特处于“0”状态。为了让XY混合器有效工作，必须以特定的形式准备这种迪克态，但这一过程非常复杂且资源密集。

传统上，创建这种状态需要精确且复杂的步骤。然而，2-Step QAOA为这一挑战提供了一个有前景的解决方案。

2-Step QAOA的理论机制

在2-Step QAOA中，第一步QAOA利用约束条件创建量子态。第二步QAOA去除这些约束条件，并使用第一步QAOA创建的量子态开始计算。QAOA基于量子退火，通过利用第一步QAOA得到的基态，使用XY混合器计算并达到要解决的另一个问题的基态。

这种方法简化了计算步骤，使得量子态的准备过程更加简单，同时留下了进一步优化的空间。

优势与应用

2-Step QAOA的主要优势在于，它使XY混合器更加易用。通过降低初始态准备的复杂性，需要使用XY混合器的算法的实现变得更加容易。

此外，该方法开辟了优化的新可能性，实现了更高效的量子计算。由于其逐步的过程，易于理解，并将成为探索或实验量子算法的研究人员的宝贵工具。

如何使用它

此算法可以使用标准的工具，如IBM的Qiskit，轻松实现。不需要特殊工具，可以适应现有工具来创建算法。

示例

在这个示例中，我们将设置一个具有三个量子比特的问题，其中仅选择一个比特。首先，我们将准备一个称为QUBO（二次无约束二进制优化）的公式，然后将其转换为可以用量子电路解决的格式，即伊辛模型。

我们在QUBO中定义变量为 (x_0, x_1, x_2)，量子比特为 (q_0, q_1, q_2)。变量 (x) 取值为0和1，量子比特 (q) 取值为+1和-1。我们为 (q_1) 分配一个权重为10，以鼓励选择它。这需要约束条件和一个成本函数。

这个示例改编自以下文章：

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

我们将从约束条件开始（稍后将其转换为 (q)）：

(x_0 + x_1 + x_2 - 1)^2

选择 (q_1) 的条件：

10 \times q_1

我们先从创建初始态开始。我们将使用2-Step QAOA，通过H门创建叠加态，然后选择X门作为混合器，并在QAOA中应用约束条件。

让我们在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

加载工具并准备初始态：

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

接下来，我们将约束条件转换为QAOA。我们将手动输入公式并使用sympy进行计算。让我们将变量 (x) 转换为 (q)（在哈密顿量中表示为Z）。

为了匹配QUBO中的值，其中 (x=0) 对应 (z=-1) 而 (x=1) 对应 (z=1)，我们将代入 (-z = 2x - 1)。

import sympy as sp

# 定义变量
x0, x1, x2, z0, z1, z2 = sp.symbols('x0 x1 x2 z0 z1 z2')

# 定义表达式
expression = (x0 + x1 + x2 - 1)**2

# 展开表达式
expanded_expression = sp.expand(expression)

print(expanded_expression)

# 将 x^2 替换为 x
substituted_expression = expanded_expression.subs({x0**2: x0, x1**2: x1, x2**2: x2})

print(substituted_expression)

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

# 再次展开
expanded_final_expression = sp.expand(final_expression)

# 将分数转换为小数
decimal_expression = sp.N(expanded_final_expression)

# 显示结果
print(decimal_expression)

结果为：

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

我们将手动将其实现到QAOA中，排除掉常数1.0。

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

# 定义成本哈密顿量
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'))

结果为：

{   '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.69265504]),
    'optimal_value': -0.10535746385765882,
    'optimizer_evals': None,
    'optimizer_result': <qiskit_algorithms.optimizers.optimizer.OptimizerResult object at 0x7f34b99d5de0>,
    'optimizer_time': 2.2393693923950195}

接下来我们检查一下电路：

我们可以使用 assign_parameters 将得到的电路和参数用于QAOA执行。

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)

结果为：

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

我们已经取得了一些进展。虽然还不是完美的迪克态，但进一步迭代似乎可以实现。

接下来，我们将使用创建的状态作为初始态，并再次执行QAOA。

成本哈密顿量为 (H_{c_2} = 10Z_1)。
这次我们将使用XY混合器。

在此之前，我们需要在Qiskit中进行一些操作。

之前生成的量子电路包括测量。我们希望重用该电路，但需要移除测量部分，因此我们将门操作复制到一个新的电路中。

# 创建一个不包含测量的新电路
new_circuit = QuantumCircuit(bound_circuit.num_qubits)

# 将非测量指令添加到新电路中
for instr, qargs, cargs in bound_circuit.data:
    if instr.name != "measure":
        new_circuit.append(instr, qargs, cargs)

# 替换原始电路
bound_circuit = new_circuit
display(new_circuit.draw('mpl'))

现在我们进行计算。
准备XY混合器。每个量子比特相互连接，并且成本仅施加到中间的量子比特 (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)

结果为：

{   '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}

成功输出010。我们再一次执行状态矢量。

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}

取得了大成功。

结论

2-Step QAOA的引入标志着量子计算领域的重大进步。通过简化与XY混合器兼容的量子态的准备，该技术有潜力使先进的量子算法变得更加实用且易于访问。随着量子计算的不断发展，2-Step QAOA这样的创新将在塑造这一令人兴奋领域的未来方面发挥重要作用。

在本博客中，我们简要介绍了2-Step QAOA的潜力。如果您想进一步了解该方法的技术方面和应用，建议您探索该领域的最新研究和发展。