SciPost Submission Page
Quantum Approximate Optimization for Hard Problems in Linear Algebra
by Ajinkya Borle, Vincent E. Elfving, Samuel J. Lomonaco
- Published as SciPost Phys. Core 4, 031 (2021)
|As Contributors:||Ajinkya Borle|
|Date submitted:||2021-09-04 04:29|
|Submitted by:||Borle, Ajinkya|
|Submitted to:||SciPost Physics Core|
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
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.
Submission & Refereeing History
You are currently on this page
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.
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. , 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 https://scipost.org/SciPostPhys/authoring.
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.  has in the meantime appeared in Phys. Rev. A 104, 032422 (2021).
8- The full journal reference for Ref.  is Science Bulletin 66, 2181 (2021), compare again item 5.
9- Ref.  has a DOI (!), but the list of authors is very different from what I find on zenodo.
10- Ref.  still has the strange "p¿1" in its title that I already pointed out in my first report.
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.