Examples: MaxCut¶
In this section, we present three implementations to solve the Max-Cut problem using quantum computing: QAOA [8], FALQON [7], and VQE [9]. Here, our strict focus is on their implementation in Ket; for detailed algorithmic presentations, we refer the reader to the original works. The Max-Cut problem seeks to partition the vertices of a graph into two disjoint sets such that the number of edges spanning the two sets is maximized.
Defining the Hamiltonians¶
For QAOA, FALQON, and VQE, the objective of Max-Cut can be encoded into a cost Hamiltonian \(H_c\). For a graph with edges \(\mathcal{E}\), the cost Hamiltonian assigns a lower energy to valid bitstrings representing the cuts. Additionally, for QAOA and FALQON, we require a mixer Hamiltonian \(H_m\) to drive transitions between states.
Cost Hamiltonian:
def cost_h(edges, q: Quant):
with obs():
hc = sum(1 - Z(q[a]) * Z(q[b])
for a, b in edges)
return -hc / 2
Mixer Hamiltonian:
def mixer_h(nodes: Quant):
with obs():
Hm = sum(X(q) for q in nodes)
return Hm
QAOA¶
The QAOA ansatz consists of alternating applications of the time-evolution operators \(e^{-i \gamma H_c}\) and \(e^{-i \beta H_m}\). Since the terms within \(H_c\) and \(H_m\) mutually commute, we can pass these Hamiltonians directly to Ket’s evolve function.
def qaoa_layer(edges, qubits, gamma, beta):
evolve(gamma * cost_h(edges, qubits))
evolve(beta * mixer_h(qubits))
def qaoa_ansatz(edges, qubits, gamma, beta):
for g, b in zip(gamma, beta):
qaoa_layer(edges, qubits, g, b)
A classical optimizer is needed to execute this algorithm. To use SciPy’s scipy.optimize.minimize, we must create a cost function that encapsulates the quantum process:
def qaoa_objective(graph, n, parameters):
process = Process(num_qubits=n, simulator="dense",
execution="batch")
p = len(parameters) // 2 # Number of layers
gamma = parameters[p:]
beta = parameters[:p]
qubits = process.alloc(n)
H(qubits) # Prepare the initial uniform superposition
qaoa_ansatz(graph, qubits, gamma, beta)
return exp_value(cost_h(graph, qubits)).get()
res = minimize(
partial(qaoa_objective, graph, n),
parameters, # Initial parameters
method="COBYLA", # Gradient-free optimizer
)
VQE¶
Unlike QAOA, VQE does not prescribe a rigidly structured ansatz. A possible, hardware-efficient implementation for the Max-Cut problem is as follows:
def vqe_ansatz(graph, qubits, parameters):
for p in parameters:
for a, b in graph:
CZ(qubits[a], qubits[b])
RY(p, qubits)
As with QAOA, we need an objective function to utilize the SciPy minimizer. It is common to use gradient-based optimizers for VQE; here, we implement the objective function so that the gradient is calculated and returned alongside the cost value:
def vqe_objective(graph, n, parameters):
process = Process(num_qubits=n, simulator="dense",
execution="batch", gradient=True)
# Register parameters for gradient calculation
parameters = process.param(*parameters)
qubits = process.alloc(n)
vqe_ansatz(graph, qubits, parameters)
return (
exp_value(cost_h(graph, qubits)).get(),
[p.grad for p in parameters],
)
res = minimize(
partial(vqe_objective, graph, n),
parameters, # Initial parameters
method="L-BFGS-B", # Gradient-based optimizer
jac=True,
)
FALQON¶
FALQON utilizes a different approach from QAOA and VQE; it relies on feedback-based measurements to iteratively optimize the quantum state over several layers.
def falqon_layer(graph, qubits, beta, delta_t):
evolve(delta_t * cost_h(graph, qubits))
evolve(beta * delta_t * mixer_h(qubits))
def beta_h(graph, qubits):
return -1j * commutator(mixer_h(qubits), cost_h(graph, qubits))
In Ket, we can use the KBW simulator and live execution to calculate the feedback parameter \(\beta\) and the cost expectation \(\langle H_c \rangle\) interactively for each layer.
beta, cost = [0.0], []
process = Process()
qubits = H(process.alloc(n))
for _ in range(num_layers):
falqon_layer(graph, qubits, beta[-1], delta_t)
cost.append(exp_value(cost_h(graph, qubits)).get())
beta.append(exp_value(beta_h(graph, qubits)).get())