Optimization and Ensemble Methods

Optimization and Ensemble Methods#

Quantum-enhanced optimization: QAOA for combinatorial problems, quantum approximate counting, and quantum boosting.

Combinatorial optimization and ensemble learning are two areas where quantum computing may offer near-term advantages. QAOA provides a structured approach to optimization on quantum hardware, while quantum-enhanced ensemble methods explore whether quantum sampling can improve boosting and bagging techniques.

QAOA for Combinatorial Optimization#

QAOA (covered in depth in Adiabatic Quantum Computing) is the primary quantum algorithm for combinatorial optimization on gate-model hardware. Here we focus on how specific problems are encoded and solved.

Problem Encoding: QUBO and Ising#

Many combinatorial problems can be expressed as Quadratic Unconstrained Binary Optimization (QUBO):

\[\min_{\mathbf{x} \in \{0,1\}^n} \mathbf{x}^T Q \mathbf{x}\]

The QUBO-to-Ising mapping $x_i = (1 - \sigma_i^z)/2$ converts this to finding the ground state of:

\[H_C = \sum_{i<j} J_{ij}\,\sigma_i^z\sigma_j^z + \sum_i h_i\,\sigma_i^z + \text{const}\]

Example Problems#

Problem	Ising Encoding	Qubits	Two-Body Terms
MaxCut	$H_C = \sum_{(i,j)\in E} \frac{1}{2}(1 - \sigma_i^z\sigma_j^z)$	$	V
Max-SAT	Clause penalties	$n$ variables	$O(n^2)$
Portfolio optimization	Quadratic risk + return	$n$ assets	$O(n^2)$
Traveling salesman	One-hot city encoding	$n^2$	$O(n^4)$
Graph coloring	Color assignment	$n \cdot k$	$O(

Qubit overhead

The number of qubits required often exceeds the natural problem size. TSP with $n$ cities requires $n^2$ qubits in the standard one-hot encoding. Penalty terms for constraints further increase circuit complexity. This overhead limits the problem sizes tractable on near-term hardware.

Warm-Starting QAOA#

Standard QAOA initializes in the uniform superposition $|+\rangle^{\otimes n}$. Warm-starting techniques initialize from a classically computed approximate solution, biasing the quantum search toward promising regions:

\[|\psi_0\rangle = \bigotimes_{i=1}^{n} \left(\cos\frac{\alpha_i}{2}|0\rangle + \sin\frac{\alpha_i}{2}|1\rangle\right)\]

where $\alpha_i$ is derived from a classical relaxation. Warm-started QAOA can outperform standard QAOA at low depth.

Quantum Approximate Counting#

Quantum approximate counting estimates the number of solutions to a search problem. Given an oracle that marks solutions, the quantum counting algorithm combines Grover’s operator with quantum phase estimation to estimate:

\[\theta = \arcsin\sqrt{M/N}\]

where $M$ is the number of solutions out of $N$ total possibilities. This requires $O(\sqrt{N/M})$ oracle calls, a quadratic improvement over classical counting.

Applications in ML include:

Estimating the size of hypothesis classes
Counting satisfying assignments in constraint satisfaction
Estimating partition functions

Quantum Boosting#

Boosting algorithms (AdaBoost, gradient boosting) combine weak learners into a strong ensemble. Several quantum enhancements have been proposed:

Quantum Sampling for Boosting#

Classical boosting updates a distribution over training examples, emphasizing misclassified points. Quantum computers can prepare and sample from distributions more efficiently in certain cases:

Grover-enhanced sampling: Use amplitude amplification to sample from the re-weighted distribution, achieving quadratic speedup in drawing hard-to-find misclassified examples.
Quantum random access: Store the distribution in a quantum state and perform amplitude estimation to identify the most important training examples.

QBoost#

The QBoost algorithm (Neven et al., 2012) formulates the boosting problem as a QUBO:

\[\min_{\mathbf{w} \in \{0,1\}^T} \sum_{s=1}^{S}\left(\frac{1}{T}\sum_{t=1}^{T} w_t\, h_t(x_s) - y_s\right)^2 + \lambda \sum_t w_t\]

where $h_t$ are weak classifiers and $w_t$ are binary selection variables. This can be solved on a quantum annealer or via QAOA. The quantum advantage lies in exploring the exponentially large space of ensemble combinations.

Quantum Random Forests#

Random forests aggregate predictions from decision trees trained on random subsets of features and data. Quantum enhancements include:

Quantum feature selection: Use Grover search to find optimal feature subsets.
Quantum majority voting: Amplitude estimation for computing the ensemble vote more efficiently than classical counting.
Tensor network ensembles: Represent the ensemble as a tensor network, potentially enabling more expressive combinations.

Code Examples#

Qiskit

from qiskit.circuit import QuantumCircuit, Parameter
from qiskit.primitives import StatevectorEstimator
from qiskit.quantum_info import SparsePauliOp
from scipy.optimize import minimize
import numpy as np

# MaxCut on a triangle graph
edges = [(0,1), (1,2), (0,2)]
n_qubits = 3
p = 1

# Cost Hamiltonian: sum of 0.5*(1 - ZiZj) for each edge
terms = []
for i, j in edges:
    label = ['I'] * n_qubits
    label[i] = 'Z'
    label[j] = 'Z'
    terms.append((''.join(reversed(label)), -0.5))
terms.append(('I' * n_qubits, 0.5 * len(edges)))
H_cost = SparsePauliOp.from_list(terms)

gamma = Parameter('γ')
beta = Parameter('β')

qc = QuantumCircuit(n_qubits)
qc.h(range(n_qubits))
# Cost layer
for i, j in edges:
    qc.cx(i, j)
    qc.rz(2 * gamma, j)
    qc.cx(i, j)
# Mixer layer
for i in range(n_qubits):
    qc.rx(2 * beta, i)

estimator = StatevectorEstimator()

def cost(params):
    bound = qc.assign_parameters({gamma: params[0], beta: params[1]})
    job = estimator.run([(bound, H_cost)])
    return -job.result()[0].data.evs  # maximize cut

result = minimize(cost, np.random.randn(2), method='COBYLA')
print(f"MaxCut value: {-result.fun:.4f}")

Cirq

import cirq
import numpy as np
from scipy.optimize import minimize

qubits = cirq.LineQubit.range(3)
edges = [(0,1), (1,2), (0,2)]

def qaoa_maxcut(params):
    gamma, beta = params
    circuit = cirq.Circuit()
    circuit.append(cirq.H.on_each(*qubits))
    for i, j in edges:
        circuit.append(cirq.ZZPowGate(exponent=gamma/np.pi).on(qubits[i], qubits[j]))
    for q in qubits:
        circuit.append(cirq.rx(2*beta).on(q))
    sim = cirq.Simulator()
    state = sim.simulate(circuit).final_state_vector
    # Compute MaxCut cost
    cost = 0
    for i, j in edges:
        Z = np.ones(8)
        for k in range(8):
            bi = (k >> i) & 1
            bj = (k >> j) & 1
            Z[k] = 1 if bi != bj else 0
        cost += np.sum(np.abs(state)**2 * Z)
    return -cost

result = minimize(qaoa_maxcut, np.random.randn(2), method='COBYLA')
print(f"MaxCut value: {-result.fun:.4f}")

PennyLane

import pennylane as qml
from pennylane import numpy as np

n_qubits = 3
edges = [(0,1), (1,2), (0,2)]
dev = qml.device("default.qubit", wires=n_qubits)

cost_h = qml.Hamiltonian(
    [0.5]*len(edges),
    [qml.Identity(0) - qml.PauliZ(i) @ qml.PauliZ(j) for i, j in edges]
)

@qml.qnode(dev)
def qaoa(gamma, beta):
    for i in range(n_qubits):
        qml.Hadamard(wires=i)
    for i, j in edges:
        qml.CNOT(wires=[i, j])
        qml.RZ(2 * gamma, wires=j)
        qml.CNOT(wires=[i, j])
    for i in range(n_qubits):
        qml.RX(2 * beta, wires=i)
    return qml.expval(cost_h)

opt = qml.AdamOptimizer(0.1)
params = np.array([0.5, 0.5], requires_grad=True)
for _ in range(50):
    params = opt.step(lambda p: -qaoa(p[0], p[1]), params)
print(f"MaxCut value: {qaoa(params[0], params[1]):.4f}")

PyQuil

from pyquil import Program
from pyquil.gates import H, CNOT, RZ, RX, MEASURE
from pyquil.api import WavefunctionSimulator
import numpy as np
from scipy.optimize import minimize

edges = [(0,1), (1,2), (0,2)]
n_qubits = 3
sim = WavefunctionSimulator()

def cost(params):
    gamma, beta = params
    prog = Program()
    for i in range(n_qubits):
        prog += H(i)
    for i, j in edges:
        prog += CNOT(i, j)
        prog += RZ(2*gamma, j)
        prog += CNOT(i, j)
    for i in range(n_qubits):
        prog += RX(2*beta, i)
    wf = sim.wavefunction(prog).amplitudes
    # MaxCut cost
    val = 0
    for i, j in edges:
        for k in range(2**n_qubits):
            bi, bj = (k >> i) & 1, (k >> j) & 1
            val += abs(wf[k])**2 * (bi != bj)
    return -val

result = minimize(cost, np.random.randn(2), method='COBYLA')
print(f"MaxCut value: {-result.fun:.4f}")