PCE (Pauli Correlation Encoding)

Pauli Correlation Encoding (PCE)

PCE is a qubit-efficient encoding for QUBO (Quadratic Unconstrained Binary Optimization) problems. Instead of the standard one-qubit-per-variable mapping, PCE encodes N binary variables into only ⌈log₂(N)⌉ qubits by mapping each variable to the parity of a subset of measured qubits.

This makes PCE particularly attractive for solving large combinatorial optimization problems on near-term quantum hardware, where qubit count is the primary bottleneck.

How It Works

In standard QUBO encoding, N variables require N qubits. PCE instead:

1. Maps each variable xᵢ to a parity function of measured bitstrings, defined by a bitmask
2. Uses only ⌈log₂(N)⌉ qubits (dense encoding) or slightly more (polynomial encoding)
3. Optimizes a parameterized circuit to minimize the QUBO cost function via parity expectations

The optimization uses a two-phase approach:

• Soft energy (α < 5.0): Relaxed VQE with smooth gradients for exploration
• Hard CVaR energy (α ≥ 5.0): Conditional Value-at-Risk for final convergence

Encoding Types

Code Example

import numpy as np
from divi.qprog import PCE
from divi.qprog.optimizers import ScipyOptimizer, ScipyMethod
from divi import ParallelSimulator

# A 10-variable QUBO (only 4 qubits needed with dense encoding!)
qubo_matrix = np.random.uniform(-1, 1, (10, 10))
qubo_matrix = (qubo_matrix + qubo_matrix.T) / 2  # Symmetrize

pce = PCE(
    qubo_matrix=qubo_matrix,
    encoding_type="dense",
    optimizer=ScipyOptimizer(ScipyMethod.COBYLA),
    max_iterations=50,
    backend=ParallelSimulator(),
)

pce.run()

print(f"Solution: {pce.solution}")
print(f"Qubits used: {pce.n_qubits} (vs {qubo_matrix.shape[0]} variables)")

BinaryQuadraticModel Support

PCE also accepts D-Wave’s BinaryQuadraticModel directly:

import dimod

bqm = dimod.generators.randint(20, vartype="BINARY", low=-5, high=5, seed=42)

pce = PCE(
    qubo_matrix=bqm,
    encoding_type="dense",
    optimizer=ScipyOptimizer(ScipyMethod.COBYLA),
    max_iterations=50,
    backend=ParallelSimulator(),
)

Top-N Solutions

PCE provides decoded solutions via the get_top_solutions() method:

top = pce.get_top_solutions(n=5, include_decoded=True)
for sol in top:
    print(f"Bitstring: {sol.bitstring}, Probability: {sol.probability:.4f}")
    print(f"  Decoded QUBO assignment: {sol.decoded}")

Each SolutionEntry contains:

• bitstring: The raw measured qubit state
• probability: Measurement probability
• decoded: The QUBO variable assignment (binary array)

Custom Bitstring Decoding

For advanced use cases, you can provide a custom decoding function:

pce = PCE(
    qubo_matrix=qubo_matrix,
    decode_parities_fn=my_custom_decoder,
    ...
)

When to Use PCE

• Large QUBOs (N > 20 variables): PCE’s logarithmic scaling becomes a significant advantage
• Qubit-constrained hardware: When available qubits are limited
• Benchmarking: Compare PCE solutions against classical solvers to evaluate quantum advantage
• Combinatorial optimization: Any problem expressible as a QUBO matrix