Source-linked AI summary
Quantum Approximate Optimization for Hard Problems in Linear Algebra
Ajinkya Borle, Vincent E. Elfving, Samuel J. Lomonaco
TL;DR
The paper asks whether QAOA can address BLLS, an NP-hard building block for NBMF and related NMF problems. It formulates BLLS for QAOA and evaluates noiseless simulations, noise models, and IBM Q processors, finding that Simulated Annealing outperforms QAOA for p ≤3 in ground-state sampling while current hardware remains challenging.
Problem
Method
The paper formulates BLLS for QAOA and evaluates it with noiseless simulations, device-realistic noise models, and IBM Q processors.
Source: §I · p. 1, §IV · p. 12Results
Simulated Annealing can outperform QAOA for p ≤3 and n > 8 in the probability of sampling the BLLS ground state.
Source: §IV · p. 12Takeaways & Limitations
QAOA provides a sampled-output approach for hard linear-algebra problems, but current hardware still struggles with the required circuits.
Source: §I · p. 1, §IV · p. 12Current devices remain challenged by implementing linear-depth, high-connectivity circuits for this application.
Source: §IV · p. 12
Abstract
from arXiv · showhide
The Quantum Approximate Optimization Algorithm (QAOA) by Farhi et al. is a quantum computational framework for solving quantum or classical optimization tasks. Here, we explore using QAOA for Binary Linear Least Squares (BLLS); a problem that can serve as a building block of several other hard problems in linear algebra, such as the Non-negative Binary Matrix Factorization (NBMF) and other variants of the Non-negative Matrix Factorization (NMF) problem. Most of the previous efforts in quantum computing for solving these problems were done using the quantum annealing paradigm. For the scope of this work, our experiments were done on noiseless quantum simulators, a simulator including a device-realistic noise-model, and two IBM Q 5-qubit machines. We highlight the possibilities of using QAOA and QAOA-like variational algorithms for solving such problems, where trial solutions can be obtained directly as samples, rather than being amplitude-encoded in the quantum wavefunction. Our numerics show that Simulated Annealing can outperform QAOA for BLLS at a QAOA depth of $p\leq3$ for the probability of sampling the ground state. Finally, we point out some of the challenges involved in current-day experimental implementations of this technique on cloud-based quantum computers.
I. INTRODUCTION
The paper proposes QAOA for binary linear least squares, an NP-hard problem that can support non-negative matrix factorization variants. BLLS is connected to NBMF through alternating least squares, with broader applications in dimensionality reduction and data analysis.
I. INTRODUCTION
1. The binary linear least squares (BLLS) problem
- BLLS is NP-hard and can serve as a building block for other hard linear-algebra problems, including NBMF.Multiple binary variables can represent fixed-point approximations of real variables.Source: §1 · p. 2
2. Non-negative Matrix Factorization (NMF) and variants
- NMF performs non-negative linear dimensionality reduction by approximating V with W × H, producing sparse and interpretable factors.Applications include facial analysis, astronomy, and topic modeling.Source: §2 · p. 2
- NBMF restricts H to binary entries, yielding sparser factors and more holistic learned features than general NMF.For facial extraction, NBMF features can resemble complete faces rather than facial parts.Source: §2 · p. 2
- Alternating least squares uses BLLS for NBMF’s column-update step, while the corresponding row-update step is solved classically.This identifies the specific point in the factorization pipeline where QAOA could be applied.Source: §2 · p. 2
- The paper positions QAOA as an alternative to earlier quantum-annealing approaches for NBMF and related NMF problems.The proposed alternative is presented as a direction for future exploration.Source: §2 · p. 2
3. Quadratic Unconstrained Binary Optimization (QUBO)
The paper maps binary optimization into QUBO and then into an Ising Hamiltonian for QAOA. QAOA alternates cost and driver operations, evaluates sampled energies, and uses classical optimization to update its angles.
3. Quadratic Unconstrained Binary Optimization (QUBO)
- QUBO provides an NP-hard intermediate formulation in which binary variables have linear and quadratic coefficients.Many application-domain problems map naturally to QUBO.Source: §3 · p. 2
4. The Quantum Approximate Optimization Algorithm (QAOA)
- Ising encoding represents binary optimization with single-qubit fields and pairwise couplings, then maps the objective to qubits.The paper notes that efficient quantum solutions to NP-complete problems remain unknown.Source: §4 · p. 3
- QAOA applies cost and transverse-field Hamiltonians repeatedly at depth p, using angle sets γ and β to generate candidate states.The qubits begin in a uniform computational-basis superposition.Source: §4 · p. 3
- A classical black-box optimizer updates 2p angles from expectation values estimated from repeated QAOA measurements.The final sampled bitstring with lowest energy is selected as the result.Source: §4 · p. 3
- QAOA is designed for low-depth gate-model circuits, with the intended advantage arising when p ≪ n while efficiently sampling good solutions.Its suitability is therefore tied to shallow circuits and scalable sampling.Source: §4 · p. 3
5. Implicit filtering optimization
The paper uses Implicit Filtering to optimize QAOA angles from noisy expectation values. ImFil is a bounded, derivative-free black-box method designed for noisy objective evaluations.
5. Implicit filtering optimization
- ImFil is the chosen optimizer for QAOA because expectation values are approximate and noisy.It suggests parameter updates without requiring derivative information.Source: §5 · p. 4
- Implicit Filtering is a bounded, derivative-free black-box optimization technique that accommodates noise while minimizing the objective.The paper contrasts it with alternatives including Bayesian Optimization, COMPASS, and SPSA.Source: §5 · p. 4
B. Related work
Earlier quantum linear-algebra algorithms often encode outputs in quantum amplitudes and require fault-tolerant hardware, whereas this work targets directly sampled bitstrings for hard binary problems. QAOA is presented as a gate-based alternative to quantum annealing, but practical connectivity and hardware constraints remain significant.
B. Related work
- Amplitude-encoded quantum linear-system and least-squares algorithms require fault-tolerant computers and make classical output extraction difficult.Input-state preparation and measurement can undermine their practical near-term utility.Source: B. Related work · p. 4
- Quantum annealing studies used Ising formulations whose computational-basis measurements directly encode binary solutions, but speedup comparisons remain difficult under noisy implementations.Prior work reported benefits from combining forward and reverse annealing, with one study finding a 12% improvement over forward annealing at added run cost.Source: B. Related work · p. 4
- The paper differs from related variational algorithms by targeting hard problems rather than problems that are convex and classically polynomial-time solvable.Its sampled-output framing also differs from approaches that encode results as amplitudes.Source: B. Related work · pp. 4–5
- QAOA alternates cost and driver Hamiltonians like a bang-bang annealing schedule while offering gate-based programmability for mapping problem graphs.The paper contrasts this flexibility with connectivity challenges in annealing architectures.Source: B. Related work · pp. 4–5
A. Problem formulation
- For BLLS, the number of qubits depends only on the binary variable vector, while matrix and right-hand-side data are classically preprocessed into QUBO coefficients.The QUBO is then converted to an Ising objective up to an optimization-irrelevant offset.Source: A. Problem formulation · p. 5
B. Mapping to quantum gates
The BLLS Hamiltonian is simulated by decomposing commuting cost and mixing Hamiltonians into implementable quantum gates. Two-qubit ZZ interactions use gate templates that can be generalized beyond adjacent qubits.
B. Mapping to quantum gates
- Commuting components of the cost Hamiltonian allow its simulation to be decomposed into angle-parameterized terms.The decomposition uses the cost-Hamiltonian angle γ_l.Source: B. Mapping to quantum gates · p. 5
- The exponential of the mixing Hamiltonian is likewise broken down into implementable components.Source: B. Mapping to quantum gates · p. 5
- Two-qubit components require a gate combination implementing interactions, while single-qubit terms can use individual gates.The template is introduced for components of Eqn(18) requiring two-qubit interaction.Source: B. Mapping to quantum gates · p. 5
- The ZZ-interaction strategy extends from adjacent qubits to arbitrary qubit pairs in the system.Appendix B provides an example QAOA circuit for BLLS.Source: B. Mapping to quantum gates · p. 5
1. For IBM Q specific gates
The experiments use IBM Q devices with platform-specific basis gates, including U1, U2, U3, CX, RZ, SX, and X operations. Practical implementations must also account for limited qubit connectivity and SWAP-based logical replacement.
1. For IBM Q specific gates
- IBM Q London and Athens expose different basis-gate sets, requiring attention to IBM-specific U1, U2, and U3 gates.London uses {U1, U2, U3, CNOT, I}, while Athens uses {CX, ID, RZ, SX, X}.Source: §1 · p. 5
- The U3 gate is represented through a parameterized matrix form for implementing general single-qubit operations.Source: §1 · pp. 5–6
- Limited physical connectivity means distant-qubit interactions require logical qubit replacement using SWAP operations.The paper refers to Appendix C for an IBM Q gate demonstration.Source: §1 · p. 6
C. Experiment methods
The experiments evaluate QAOA for sparse, randomly generated BLLS instances using exact statevector, shot-noise, and IBM Q device settings. Performance is assessed through ground-state sampling probability and relative expectation-value error.
C. Experiment methods
- The dataset contains 100 seeded BLLS instances for each n ∈ {3, 4, 5, 9, 10}, including consistent and inconsistent least-squares cases.Matrices are sparse with density 0.2, and problem sizes are limited to 10 qubits because classical quantum simulation scales exponentially.Source: C. Experiment methods · p. 6
- QAOA is implemented with QISKIT and optimized using ImFil, with default settings except for controlled iteration budgets.Source: C. Experiment methods · p. 6
1. Experiments with no noise
- Exact statevector experiments evaluate QAOA in a noiseless setting across depths p = 1, 2, and 3 using multiple random starts.The best result across starting points is recorded for each problem, with budgets selected so at least 70% of tests converged.Source: §1 · p. 6
2. Experiments to compare no noise and shot-noise performance
- Shot-noise experiments estimate expectation values from finite samples, introducing stochasticity despite noiseless circuit simulation.Each experiment is repeated 10 times across shot counts, using a smaller random subset because shot-noise runs are substantially slower.Source: §2 · p. 6
- The shot-noise comparison uses p = 1, 2, and 3 with reduced random-start budgets and matched statevector runs.Source: §2 · pp. 6–7
3. Experiments on an IBM Q device
- IBM Q experiments use five qubits, p = 1, 200 iterations, and 1024 shots to balance nontrivial structure against device-depth and noise constraints.Additional runs reuse statevector-optimized γ and β values to recreate distributions and expectation values on hardware.Source: §3 · p. 7
D. Results
- Performance is measured by the probability of sampling the best solution and the relative error ϵ_r of the expectation value versus ground-state energy.The relative error is zero at the ground-state energy and can exceed 1 depending on spectral width and ground-state cost.Source: D. Results · p. 7
1. Optimization trajectory for QAOA
Across four experiments, QAOA converges toward low-energy BLLS solutions, but performance depends on depth, measurement noise, problem size, and sampling method. Simulated Annealing surpasses QAOA at depth p = 3 for larger instances, while QAOA outperforms uniform random sampling in ground-state sampling.
1. Optimization trajectory for QAOA
- In one p = 1 instance, energy-expectation fluctuations decrease during optimization; statevector results provide the exact baseline, while shot-noise simulations perform relatively well against it.Source: §1 · p. 7, Figure 1 · p. 7
- The tested IBM Q devices found the best solution every time but did not approximate the theoretically optimal QAOA result distribution well.Source: §1 · p. 7
2. QAOA results with no-noise
- In noiseless simulations, relative error grows polynomially with problem size, while increasing depth from p = 1 to p = 2 helps moderately and p = 3 adds more modest improvement for larger n.The fitted form is ϵr = a × n^b, but the authors caution that stronger scaling conclusions require further experimentation.Source: §2 · pp. 7–8, Figure 2 · p. 8
3. No noise vs Shot-noise optimization
- With 2^n+2 shots, measurement-based optimization broadly resembles statevector optimization, but p = 1 and p = 2 become especially difficult to distinguish.The overlap may reflect approximate measurement results or the small number of averaged experiments.Source: §3 · p. 8, Figure 3 · p. 8
- For p = 4 and above, simulations become computationally infeasible because runtime grows exponentially with QAOA depth p.Source: §3 · p. 8
4. Probability of sampling the ground state
- Ground-state sampling was evaluated using QAOA statevector outputs, Simulated Annealing with 10 steps, and uniform random sampling, including per-query and 10-query cumulative probabilities.Source: §4 · pp. 9–10
- For n > 8, Simulated Annealing yields a higher ground-state success probability than QAOA at depth p = 3, although all methods decay exponentially with problem size.QAOA still performs much better than uniform random sampling, even at p = 1.Source: §4 · p. 10
- QAOA’s ground-state sampling advantage over uniform random sampling remains clear with up to 2^n shots because it amplifies low-energy bitstrings and suppresses higher-energy ones.Source: §4 · p. 10
5. Effect of noise on expectation value
The study evaluates how progressively scaled device noise affects QAOA expectation values for selected 5-variable BLLS instances, comparing noiseless simulation, noisy simulations, and hardware under different connectivity assumptions. Device results show higher relative error than waveform simulation, while ideal connectivity performs better than device-limited connectivity.
Experimental setup
- For each instance, noiseless p = 1 optimal (γ, β) pairs are evaluated with scaled noise models and hardware using 8192 shots.Noise is scaled down in powers of two to 2^-7, and simulations use either all-to-all or device-limited coupling maps.Source: §5 · pp. 10–11
- The experiment uses 30 randomly selected five-variable problems whose ground-state bitstrings are neither all zeros nor all ones.These instances were chosen because uniform ground-state bitstrings may be comparatively easier to sample from a QAOA circuit.Source: §5 · p. 10
- Figure 6 compares median relative errors and their median absolute deviations across scaled noise simulations, noiseless waveforms, and QPU results.Both panels use QAOA depth p = 1 and contrast device-limited with ideal all-to-all connectivity.Source: Figure 6 · p. 10
Results
- The device’s relative error in C(γ, β) is approximately 2.5 times the waveform-simulation error for these problems and parameters.The authors caution that a broader study of noise types is needed for definite conclusions.Source: §5 · p. 11
- Ideal all-to-all connectivity gives significantly better results than the device coupling map under the same noise model.The difference is mainly attributed to additional SWAP gates required by restricted connectivity.Source: §5 · p. 11
6. Effect of shot number on optimization
The experiments examine shot requirements, IBM Q device behavior, and broader theoretical and practical challenges for QAOA applied to BLLS. Overall, the work finds that low-shot optimization can remain effective in simulations, while current hardware struggles with high-connectivity variational circuits.
6. Effect of shot number on optimization
- For n = 5, Figure 7 measures optimized QAOA output-distribution relative error against shot number using medians and MAD error bars.The optimization uses finite-shot stochastic estimates, then evaluates relative error against the exact statevector expectation value.Source: Figure 7 · p. 11, §6 · p. 11
- As problem size increases, optimization often performs well with 2^(n−2) shots, suggesting the required shot count may not scale exponentially or may have a smaller exponent than uniform random sampling.The authors state that further research is needed to establish this scaling behavior.Source: §6 · p. 11
7. IBM Q device performance
- IBM Q devices always found the best solution, but required 1024 shots per QAOA iteration; fewer shots sometimes missed optimal bitstrings and further deteriorated convergence because measured distributions were poorly approximated.QV 32 came closer to the actual probability distribution than QV 16, but QV 32 was not able to efficiently do its part in the variational procedure.Source: §7 · p. 11
E. Discussion
- Sparse chip connectivity, swap routing, low two-qubit fidelity, decoherence, and unmitigated readout errors constrain real-device performance for fully connected problem graphs.The discussion identifies scaling Hamiltonian coefficients and implementing high-connectivity interactions as additional theoretical and practical challenges, with error mitigation and readout correction proposed for future work.Source: §7 · pp. 11–12, E. Discussion · p. 12
IV. CONCLUSION
- Simulated Annealing can outperform QAOA for p ≤3 when sampling BLLS ground states, while IBM Q devices remain challenging for variational optimization.The conclusion also reports that QAOA is suitable for implementing this binary optimization problem on NISQ-oriented gate-based hardware.Source: §IV · p. 12
Appendix A: Detailed QUBO Formulation for Binary Linear Least Squares
The appendix derives a QUBO formulation for BLLS by expanding the squared residual, converts it to an Ising objective, and illustrates its use in a p = 1 QAOA circuit.
Appendix A: Detailed QUBO Formulation for Binary Linear Least Squares
- BLLS is formulated by minimizing the squared residual ∥Ax − b∥2 over binary variables x.The construction begins from Ax − b and takes its 2-norm square.Source: Appendix A · p. 13
- For real A and b, expanding the squared residual yields the linear and quadratic QUBO coefficients.The coefficient expansion produces the terms used in the QUBO objective.Source: Appendix A · p. 13
- The constant term ∥b∥2 is omitted from the optimizable QUBO because it is independent of the variables.For an exact solution with ∥Ax* − b∥2 = 0, the QUBO ground-state energy is −∥b∥2.Source: Appendix A · p. 13
Appendix B: Example QAOA Circuit for BLLS
- A three-variable example has solution x* = (1, 1, 0)^T with zero residual, while retaining the same BLLS formulation.The example is categorized as a linear system of equations but uses the BLLS objective.Source: Appendix B · p. 13
- The example requires three qubits, and its QUBO is converted into an Ising objective with an offset of −11.The resulting Ising ground-state energy is −7 after accounting for the offset.Source: Appendix B · p. 13
- For p = 1, QAOA uses a circuit with a given pair of angles to calculate expectation value C(γ, β), then classically updates β and γ and repeats until convergence.Source: Appendix B · p. 13
- Measured computational-basis bitstrings are mapped to Ising eigenvalues by replacing 0 with 1 and 1 with −1 before averaging their energies.This mapping lets sampled bitstrings determine the expectation value of the diagonal cost Hamiltonian.Source: Appendix B · p. 14
Appendix C: Implementing Two-Qubit Interactions on a QPU
Dense BLLS interactions may require SWAP gates on QPUs without all-to-all connectivity, with SWAPs decomposed into CNOT gates and used to route logical qubits.
Appendix C: Implementing Two-Qubit Interactions on a QPU
- BLLS can require dense qubit connectivity, so non-all-to-all QPUs need SWAP gates to enable interactions between distant qubits.Connectivity constraints therefore affect how the logical BLLS circuit is realized on hardware.Source: Appendix C · p. 14
- A SWAP gate can be decomposed into CNOT gates for implementation on a QPU.The appendix gives the matrix and circuit decomposition of the gate.Source: Appendix C · p. 14
- On a linearly connected device, adjacent qubits are swapped to route an interaction and swapped back afterward.The compiler may use other SWAP-based realizations, and the Rz gate is also decomposed in the example.Source: Appendix C · p. 14
Appendix D: Probability Distribution of Running a QAOA Circuit for BLLS on a Real QPU
The appendix compares sampled QAOA output on simulators and IBM Q devices, analyzes fitted success-probability curves, and documents the simulated-annealing setup used for comparison.
Appendix D: Probability Distribution of Running a QAOA Circuit for BLLS on a Real QPU
- On IBM Q Athens, noise damps the highest-probability bitstrings, whereas IBM Q London produces a more even distribution with no strongly dominant ground state.The comparison uses 10,240 shots for identical optimized QAOA angles and problem instances; the noiseless simulator gives the ground state the highest probability.Source: Appendix D · p. 14, Figure 8 · p. 15
1. Curve fit
- The fitted growth model for Figure 2 is a × n^b with b = 0.85, chosen as the best compromise across the QAOA depths considered.Alternative exponents reduce fit error for individual depths but worsen fits for others.Source: §1 · p. 15, Table I · p. 15
- The exponent fit is provisional because more problem sizes n may be needed to determine a more definitive growth curve.This limitation follows directly from the limited range of problem sizes used for fitting.Source: §1 · p. 15
- The success-probability curves use 1 − (1 − a/2^(bn))^k, with k = 1 for QAOA and k = 10 for simulated annealing.For n < 3, the QAOA fit produces values above 1 in per-query curves, so the plotted probabilities are fixed to 1 as a modeling correction.Source: §1 · p. 15, Table II · p. 15
2. Simulated Annealing Experiments
- Simulated annealing experiments cover BLLS sizes 3 to 20 with temperatures T0 = 100 and Tf = 0.01 under an exponential decay schedule.Each problem is run 1,000 times, using k = 10 steps and counting ground-state outcomes for cumulative success probability.Source: §2 · p. 15