SciPost logo

SciPost Submission Page

Quantum Approximate Optimization for Hard Problems in Linear Algebra

by Ajinkya Borle, Vincent E. Elfving, Samuel J. Lomonaco

Submission summary

As Contributors: Ajinkya Borle
Preprint link: scipost_202106_00008v2
Date accepted: 2021-10-20
Date submitted: 2021-09-04 04:29
Submitted by: Borle, Ajinkya
Submitted to: SciPost Physics Core
Academic field: Physics
  • Quantum Physics
Approaches: Experimental, Computational


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 even for a small number of steps, 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.

Published as SciPost Phys. Core 4, 031 (2021)

Author comments upon resubmission

We thank the editor and the referees for taking the time to review this work. We did our best to incorporate all the changes from the referees (and have replied to each of the reports).

List of changes

Following is a list of changes now in the manuscript.

1.Commented on the expected scaling of the problem based on other works done in the field with the QAOA algorithm.
2.Added an outline of results in the introduction section.
3.Fixed the references, capitalization and spelling errors based on report 2.
4.Defined several terms that were previously taken as implicit.
5.Trimmed duplicate equations.
6.Addressed points of confusion expressed by both the reports.

Reports on this Submission

Anonymous Report 2 on 2021-10-4 (Invited Report)

  • Cite as: Anonymous, Report on arXiv:scipost_202106_00008v2, delivered 2021-10-04, doi: 10.21468/SciPost.Report.3619


1- Detailed exploration of applicability of Quantum Approximate Optimization Algorithm to Binary Linear Least Squares on Noisy Intermediate Scale Quantum Computers.
2- Test of real cloud-accessible quantum-computing devices.
3- Pedagogical text with good review of background.


1- Still on the verbose side.
2- Still a number of typographic errors.


With their revised version, the authors have addressed a big fraction of the previous criticism. I would still have number of minor, in particular typographic complaints (see "Requested changes"), but I think that these could be implemented during the production, respectively proof stage. Thus, I recommend the present version for publication in SciPost Physics Core.

Requested changes

1- Still a relatively high number of spacing errors (such as spaces before a colon ":" that should not be there).
2- The acronym "HHL" in the second line of section 2.2 can be identified from the list of authors of Ref. [53], but should really be explained in the text (or avoided, given that it only occurs once).
3- In relation to the "other point" 2 of the other Report (Report 1), there is still a "quantum Ising" in the sentence preceding the classical Ising model of Eq. (17).
4- Better insert "energy" after "ground state" in the line below Eq. (38)?
5- The references still have no DOIs. This has not only been previously requested by me, but is a highlighted item in the author guidelines, see
6- Upper- and lower-casing of titles has not really been improved. This could probably be fixed with the aid of DOIs, but see preceding item.
7- Ref. [60] has in the meantime appeared in Phys. Rev. A 104, 032422 (2021).
8- The full journal reference for Ref. [74] is Science Bulletin 66, 2181 (2021), compare again item 5.
9- Ref. [86] has a DOI (!), but the list of authors is very different from what I find on zenodo.
10- Ref. [87] still has the strange "p¿1" in its title that I already pointed out in my first report.

  • validity: good
  • significance: good
  • originality: good
  • clarity: good
  • formatting: good
  • grammar: good

Author:  Ajinkya Borle  on 2021-10-07  [id 1822]

(in reply to Report 2 on 2021-10-04)

We thank the referee for their recommendation. We apologize for the typographical errors, especially the ones pointed out before. We'll take this learning to do better henceforth in general.

Anonymous Report 1 on 2021-9-5 (Invited Report)


I find the author's responses to my questions/comments satisfactory and recommend the paper for publication in SciPost.

  • validity: -
  • significance: -
  • originality: -
  • clarity: -
  • formatting: -
  • grammar: -

Author:  Ajinkya Borle  on 2021-10-07  [id 1821]

(in reply to Report 1 on 2021-09-05)

We thank the referee for their decision (and their time and effort).

Login to report or comment