Qubit-efficient quantum combinatorial optimization solver

1. Problem Statement

Current quantum computers, particularly Noisy Intermediate-Scale Quantum (NISQ) devices, suffer from a limited qubit count (tens to hundreds) compared to the thousands of variables required for real-world combinatorial optimization problems (e.g., logistics, supply chains).

• The Bottleneck: Standard quantum algorithms, such as the Quantum Approximate Optimization Algorithm (QAOA), rely on a one-variable-to-one-qubit mapping. This makes them infeasible for large-scale problems on current hardware.
• The Trade-off: Existing "qubit-efficient" methods (e.g., circuit cutting, amplitude encoding, or decomposition) often incur massive classical computational overheads, require complex error correction, or are limited to specific problem types.
• Goal: Develop an algorithm that solves large combinatorial optimization problems using significantly fewer qubits than the number of variables ($q \ll N$) while maintaining solution quality and minimizing classical overhead.

2. Methodology

The authors propose a qubit-efficient encoding combined with a variational quantum algorithm that generalizes QAOA.

A. Qubit-Efficient Encoding (Many-to-One Mapping)

Instead of mapping $N$ variables to $N$ qubits, the algorithm maps $N$ binary variables ($z_1, \dots, z_N$) onto $q = d + \log_2(N/d)$ qubits.

• Grouping: The $N$ variables are divided into $N/d$ groups, each containing $d$ variables.
• State Representation: The solution is encoded as an entangled wave function:
  $$|\phi(z)\rangle = \sum_{\ell=0}^{N/d-1} \lambda_\ell |\ell\rangle_{\text{label}} \otimes |z_\ell\rangle_{\text{data}}$$
  • Label Qubits ($\log_2(N/d)$): Store the index $\ell$ of the group.
  • Data Qubits ($d$): Store the values of the $d$ variables in the selected group.
  • Mechanism: A projective measurement of the label qubits determines which group of variables is currently "active" in the data qubits. The full solution is stored in the superposition of these entangled states.

B. Variational Ansatz (Generalized QAOA)

The authors propose a variational circuit where the cost Hamiltonian is layer-dependent and state-dependent.

• Cost Function Estimation: Since the wave function does not hold all variables simultaneously in a product state, the cost function $C(z)$ is estimated using conditional expectation values.
  • Terms involving variables within the same group ($\ell_i = \ell_j$) are measured directly via post-selection.
  • Terms involving variables in different groups ($\ell_i \neq \ell_j$) are estimated using a mean-field approximation ($\bar{z}_i \times \bar{z}_j$).
• Hamiltonian Construction: The effective Hamiltonian $\hat{H}[\psi]$ depends on the current wave function $|\psi\rangle$ because of the non-linear nature of the cost estimation.
• Circuit Structure: The ansatz consists of alternating layers of:
  1. Mixing: Transverse field rotations ($e^{-i\beta \hat{H}_x}$).
  2. Phase Separation: Controlled unitaries ($e^{-i\gamma \hat{H}[\psi]}$) where the control is the label qubits and the target is the data qubits.
• Symmetry Breaking: The standard ansatz suffers from $Z_2$ symmetry (superposition of $z$ and $-z$), preventing convergence to the ground state cost. The authors introduce a symmetry-breaking term ($\hat{H}_z$) to bias the solution toward a specific ground state.

C. Adaptive Version

The paper also explores an Adaptive Qubit-Efficient QAOA (inspired by ADAPT-QAOA), where the mixer operators are chosen dynamically from a pool based on gradient magnitudes to construct the ansatz layer-by-layer.

3. Key Contributions

1. Novel Encoding Scheme: Introduced a generic many-to-one mapping that stores $N$ variables in $O(\log N)$ qubits (for $d=1$) or a tunable number $d + \log(N/d)$, significantly reducing qubit requirements without the exponential classical overhead of circuit cutting.
2. Generalized QAOA: Developed a variational algorithm where the cost Hamiltonian is updated classically based on measurement outcomes from the previous layer, allowing the circuit to handle the non-linear cost estimation inherent in the encoding.
3. Parameter Concentration: Demonstrated that optimal parameters for this ansatz exhibit clustering (similar to standard QAOA). Crucially, parameters optimized for a problem size $N$ can be rescaled and reused for larger $N$ (e.g., from $N=64$ to $N=128$), drastically reducing the classical optimization overhead.
4. Experimental Validation: Successfully executed a proof-of-principle experiment on Rigetti's Ankaa™-9Q-3 superconducting chip, showing high correlation (Pearson $r=0.997$) between experimental cost landscapes and noiseless simulations.

4. Results

• Benchmarking (Sherrington-Kirkpatrick Models):
  • Tested on SK spin-glass models with $N=64$ and $N=128$ variables.
  • Performance: The algorithm achieved approximation ratios comparable to standard QAOA ($d=N$) but with significantly fewer qubits.
    • Example: An ansatz with $d=2$ (using only 8 qubits for $N=64$) achieved results comparable to standard QAOA with $p=1$ layer, despite using 8x fewer qubits.
    • The $d=1$ case (using $\approx 7$ qubits for $N=64$) outperformed standard QAOA with $p=2$ layers.
• Parameter Rescaling:
  • Optimal parameters $\gamma$ were found to scale as $\gamma \propto d/N^{3/2}$.
  • Using parameters optimized for $N=64$ and rescaling them allowed the algorithm to solve $N=128, 256, 512$ instances with high accuracy, confirming the parameter concentration property.
• Adaptive Approach:
  • The adaptive version showed steady improvement in approximation ratios with depth $p$, though it saturated earlier than the fixed-structure ansatz in some cases, suggesting room for optimization in the mixer pool selection.
• Hardware Performance:
  • Experimental results on the 9-qubit Rigetti chip showed a $\sim15\%$ reduction in cost magnitude due to noise, but the landscape structure remained intact, validating the feasibility of the approach on near-term hardware.

5. Significance and Future Outlook

• Near-Term Utility: This approach enables the solution of optimization problems with hundreds of variables on current small-scale quantum devices (tens of qubits), bridging the gap between NISQ capabilities and practical problem sizes.
• Scalability: The parameter concentration property suggests that as quantum hardware scales, the classical cost of finding optimal parameters will not scale linearly with problem size, making the algorithm highly efficient.
• Fault Tolerance: The method is applicable to future fault-tolerant small-scale quantum computers, offering a way to solve large problems even if logical qubit counts remain limited.
• Versatility: While tested on SK models, the encoding and ansatz are general and can be extended to other combinatorial problems (QUBO, MaxCut) and potentially quantum machine learning applications.

Conclusion: The paper presents a robust framework for overcoming the qubit bottleneck in quantum optimization. By leveraging entangled wave functions and state-dependent Hamiltonians, it achieves high-quality solutions with a fraction of the qubits required by traditional methods, validated both numerically and experimentally.