SciPost Submission Page
Quantum Approximate Optimization for Hard Problems in Linear Algebra
by Ajinkya Borle, Vincent E. Elfving, Samuel J. Lomonaco
This Submission thread is now published as
Submission summary
| Authors (as registered SciPost users): | Ajinkya Borle |
| Submission information | |
|---|---|
| Preprint Link: | scipost_202106_00008v2 (pdf) |
| Date accepted: | 2021-10-20 |
| Date submitted: | 2021-09-04 04:29 |
| Submitted by: | Borle, Ajinkya |
| Submitted to: | SciPost Physics Core |
| Ontological classification | |
|---|---|
| Academic field: | Physics |
| Specialties: |
|
| Approaches: | Experimental, Computational |
Abstract
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.
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.
Published as SciPost Phys. Core 4, 031 (2021)
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
Strengths
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.
Weaknesses
1- Still on the verbose side.
2- Still a number of typographic errors.
Report
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 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. [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.
Report
I find the author's responses to my questions/comments satisfactory and recommend the paper for publication in SciPost.
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).
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.