Resource-Efficient Digitized Adiabatic Quantum Factorization

Technical Summary: Resource-Efficient Digitized Adiabatic Quantum Factorization

Problem Statement
The paper addresses the challenge of implementing efficient adiabatic quantum factorization on digitized (gate-based) quantum computers. Standard approaches, such as the method proposed by Peng et al. [1], formulate integer factorization as a ground-state search for a problem Hamiltonian derived from a Polynomial Unconstrained Binary Optimization (PUBO) function. This formulation results in a Hamiltonian containing non-local three- and four-qubit interaction terms ($Z^3$ and $Z^4$). On digitized devices, these high-order interactions require decomposition into multiple native two-qubit gates (e.g., CNOTs), leading to deep circuits with high gate counts. This complexity severely limits the fidelity and scalability of the algorithm, with success probabilities dropping drastically for numbers larger than 91, even when employing machine learning techniques.

Methodology
The authors propose a novel digitized adiabatic algorithm that reformulates the factorization problem using a Quadratic Unconstrained Binary Optimization (QUBO) framework. The core methodological shift involves two key changes:

1. Kernel Subspace Encoding: Instead of encoding the solution as the ground state (zero energy minimum) of a squared function $F^2$, the authors define the problem Hamiltonian $\hat{H}_{LP}$ as the linear function $F(N, \hat{p}', \hat{q}')$ itself. In this formulation, the solution corresponds to the zero-energy eigenstate (the kernel subspace) of the Hamiltonian, which is an excited state relative to the global spectrum, rather than the ground state.
2. QUBO Formulation: By utilizing the linear function, the resulting Hamiltonian contains only two-body interactions, classifying it as a QUBO problem. This eliminates the need for the NP-hard polynomial reductions and auxiliary variables typically required to map PUBO problems to QUBO.

The algorithm is implemented using a Variational Quantum Algorithm (specifically QAOA). The protocol initializes the system in a uniform superposition state (specifically $|+\rangle|-\rangle\dots$ to align with the null-subspace of $\hat{H}_{LP}$) and evolves it using alternating unitaries derived from the cost Hamiltonian ($\hat{H}_{LP}$) and a mixing Hamiltonian ($\hat{H}_M$). The cost function minimized by classical optimizers is defined as the expectation value of the absolute value of the Hamiltonian, $C_{LP} = \langle |\hat{H}_{LP}| \rangle$, to ensure convergence to the zero-eigenvalue solution.

Key Contributions

• Circuit Simplification: The proposed QUBO approach reduces the problem Hamiltonian to two-body interactions. This eliminates the need for decomposing complex multi-qubit gates, significantly reducing the circuit depth.
• New Encoding Strategy: The paper demonstrates that adiabatic factorization can be successfully performed by targeting the kernel subspace (zero-energy excited state) rather than the ground state, bypassing the limitations of PUBO formulations.
• Robustness Analysis: The authors analyze the spectral density of the Hamiltonians, showing that the QUBO formulation offers a sparser density of states around the solution subspace compared to the PUBO formulation, which aids in avoiding local minima and barren plateaus during optimization.

Results
The authors benchmarked their QUBO-based algorithm against the standard PUBO approach for factorizing integers up to 8 bits (specifically $N=25, 119, 143$).

• Gate Complexity: For a single layer of the QAOA circuit, the QUBO approach requires significantly fewer CNOT gates. For example, factorizing $N=25$ requires 8 CNOTs per layer for the QUBO method, compared to 34 CNOTs for the PUBO method (after decomposing 3- and 4-qubit gates).
• Fidelity and Confidence: The QUBO algorithm demonstrates substantially higher fidelity in identifying the correct factors. For larger numbers like $N=119$ and $N=143$, the PUBO approach fails to concentrate probability amplitude on the correct solution, resulting in low confidence scores and high Shannon entropy. In contrast, the QUBO approach successfully populates the correct solution states.
• Cost Function Convergence: The QUBO algorithm achieves a deeper reduction in the cost function (up to 3 orders of magnitude for $N=143$) compared to the PUBO approach (up to 2 orders of magnitude), indicating more effective optimization.
• Spectral Analysis: The analysis of the energy spectra reveals that the PUBO Hamiltonian has a high density of states near the solution, creating a "flat" landscape that hinders classical optimizers. The QUBO Hamiltonian exhibits a more widely spread spectrum with larger energy gaps near the kernel subspace, facilitating better state preparation.

Significance and Claims
The paper claims that this work provides a resource-efficient pathway for digitized adiabatic quantum factorization. The primary significance lies in the substantial reduction of circuit complexity and the corresponding increase in algorithmic fidelity, making the factorization of larger integers feasible on near-term devices.

The authors emphasize that while targeting an excited state (the kernel) is challenging for quantum annealers due to the lack of ground-state decoherence protection, it is advantageous for digitized quantum annealers. In gate-based systems, where decoherence is often governed by local single-qubit decay, the reduced gate count of the QUBO approach minimizes the total runtime and exposure to errors. The results suggest that QUBO-based formulations can outperform PUBO-based ones in QAOA-based optimization, challenging previous literature that assumed PUBO was necessary or superior for certain problem structures. The work motivates further exploration of digitized adiabatic protocols for broader number-theoretic problems and complex Hamiltonians.