Associate Editor Review

Based on my evaluation of the paper and the detailed feedback received from both reviewers, I believe this manuscript presents a novel contribution to the field of quantum computing, particularly in the application of quantum algorithms for solving linear systems of equations on near-term hardware. However, there are several areas that require further attention to enhance the clarity, robustness, and completeness of the work. Below is my review:

Review of the Manuscript "A near-term quantum algorithm for solving linear systems of equations based on the Woodbury identity"

Evaluation:

This manuscript introduces a promising quantum algorithm for solving linear systems based on the Woodbury matrix identity. It aligns well with the capabilities of current Noisy Intermediate-Scale Quantum (NISQ) devices and demonstrates practical implementation on IBM’s Auckland quantum computer, solving systems with up to 16 million equations. The novelty and relevance of the algorithm, combined with experimental validation, contribute significantly to the existing literature. However, there are certain aspects that need to be addressed to ensure the rigor and clarity of the research.

Key Strengths:

1. Relevance and Application to NISQ Devices:

2. The approach is highly relevant given the current state of quantum hardware and addresses important limitations of the HHL algorithm and variational methods.

3. Experimental Validation:

4. The manuscript provides substantial experimental results, demonstrating the feasibility and practicality of the proposed method on actual quantum hardware.

5. Clear Presentation and Organization:

6. The paper is generally well-organized, providing a thorough introduction and detailed sections on the algorithm and its implementation. The example problem used for experimental validation is illustrative.

Major Revisions Required:

1. Complexity Analysis:

2. Provide a detailed analysis of the algorithm's complexity, particularly the scaling behavior with respect to the problem size (N) and rank (k). Clearly articulate the quantum and classical computational resources required and how they compare to existing approaches.

3. Practical Implementation Insights:

4. Further elaborate on how the unitaries (U_i) and (V_i) can be practically constructed and implemented, including any assumptions or limitations. This will help bridge the gap between theoretical formulations and real-world applications.

5. Classical vs. Quantum Comparison:

6. Expand the discussion comparing the proposed algorithm with classical methods. Include empirical results or theoretical analysis to demonstrate scenarios where the quantum approach offers a clear advantage, and discuss potential limitations.

7. Detailed Discussion on Error Mitigation Techniques:

8. While the manuscript employs zero-noise extrapolation and measurement error mitigation, provide a more comprehensive discussion on alternative error mitigation strategies and their applicability. Also, examine the limitations and effectiveness of the chosen methods more deeply.

9. Condition Number and Conjecture:

10. The condition number analysis in Appendix B should be substantiated either through rigorous proof or supported by additional empirical data. This is crucial for understanding the algorithm's robustness and efficiency.

11. Experimental Results and Noise Analysis:

12. The sharp decrease in accuracy for (N=2^{26}) needs thorough investigation. Provide hypotheses, detailed analysis, and potential strategies to address this drop in performance. Include error bars and statistical significance in the analysis of experimental results.

Minor Revisions:

• Consistency and Clarity:

• Ensure all mathematical notation is consistently defined and presented. Improve the readability of the manuscript by integrating figures with corresponding descriptive text.

• Typographical Errors:

• Correct minor typographical errors and ensure references are up-to-date with the most relevant work.

Conclusion:

The manuscript presents an innovative quantum algorithm with the potential to impact various fields by leveraging the Woodbury identity. Addressing the suggested revisions will greatly enhance the manuscript's clarity, rigor, and impact. I recommend the paper for publication after major revisions.

Review 1

Peer Review for Manuscript "A near-term quantum algorithm for solving linear systems of equations based on the Woodbury identity"

Manuscript Summary:

The authors introduce a quantum algorithm for solving linear systems using the Woodbury matrix identity, which lends itself well to implementation on near-term quantum devices. Compared to the Harrow-Hassidim-Lloyd (HHL) algorithm, this approach is simpler and avoids the need for complex subroutines like Hamiltonian simulation. Unlike variational methods, it does not suffer from optimization issues such as barren plateaus. The algorithm is tested experimentally on IBM's Auckland quantum computer, demonstrating the ability to estimate inner products involving the solution of systems of up to 16 million equations with 2% error.

General Comments:

The manuscript presents a novel approach well-suited to the limitations of current NISQ hardware, leveraging the Woodbury identity for potentially impactful applications. The paper is well-organized, clearly written, and provides ample background for understanding the context and significance of the proposed algorithm. Nevertheless, there are areas where clarification and further detail would enhance the presentation and rigor of the work.

Specific Comments:

Strengths:

1. Relevance and Novelty:
   • The algorithm addresses an important problem with practical relevance and does so in a manner that is compatible with current quantum hardware.
2. Detailed Experimental Validation:
   • The experimental results showcase the practical implementation and feasibility of the algorithm, pushing the frontier of problem sizes solved using quantum computers.
3. Thorough Background and Literature Context:
   • The introduction and related work sections adequately cover existing methods and the motivation for proposing this alternative approach.

Weaknesses:

1. Complexity Analysis:
   • While the condition number's role is discussed, a more in-depth analysis of the algorithm's complexity, particularly the scaling behavior with respect to the problem size (N) and rank (k), would be beneficial.
2. Clarity on Practical Implementation:
   • Further discussion on how unitary operators (U_i), (V_i), and corresponding states can be constructed for practical applications would address potential concerns about real-world usability.
3. Classical-Quantum Comparison:
   • The comparison with classical algorithms should be expanded, possibly including empirical results or theoretical analysis comparing performance directly against state-of-the-art classical solvers.

Detailed Comments:

1. Complexity and Resource Analysis:

   • The complexity in terms of gate counts and depth for practically relevant problem sizes should be included. Explicit scaling behavior with respect to both (N) and (k) would provide crucial insights into the algorithm's practical limits and advantages.
   • Provide a more detailed discussion on the potential quantum advantage, considering both theoretical and empirical perspectives, especially addressing scenarios where classical counterparts might be infeasible.

2. Inner Product Computation:

   • Clarify the operational context for practical inner product computation, such as assumptions about the availability and construction of the necessary unitaries ($U_i$, $V_i$).
   • Address possible strategies to optimize or parallelize the inner product estimation process, which is central to the algorithm's efficiency.

3. Error Mitigation Techniques:

   • While zero-noise extrapolation and measurement error mitigation are employed, the discussion would benefit from mentioning other possible error mitigation strategies and potential improvements.
   • Elaborate on the limitations and potential drawbacks of the chosen error mitigation techniques, especially in larger-scale applications.

4. Experimental Results:

   • The sharp decrease in accuracy for (N=2^{26}) needs more detailed exploration, including hypotheses or analysis of causes, as well as potential strategies for addressing such sudden inaccuracies.
   • More detailed statistical analysis of the experimental results would improve the presentation, including error bars and discussion of statistical significance.

5. Broader Impact:

   • Discuss potential applications and broader impacts more comprehensively. Specifically, how might this algorithm influence fields such as machine learning, optimization, and other scientific computing domains?
   • Provide concrete examples or case studies where the algorithm's specific strengths (simplicity and applicability to near-term hardware) offer clear, compelling benefits.

Minor Comments and Suggestions:

• Ensure all equations and notation are consistently presented and defined.
• Improve the readability of some sections by integrating figures directly corresponding to the text discussing them, allowing readers to immediately visualize experimental results and concepts.
• Correct minor typographical errors and ensure that all references are to the latest relevant work.

Conclusion:

The manuscript presents a compelling quantum algorithm well-suited for near-term hardware, addressing a critical problem with innovative use of the Woodbury identity. With some enhancements in the complexity analysis, practical implementation details, and a deeper exploration of experimental findings, this work can make a strong impact and serve as a valuable resource for researchers and practitioners in quantum computing.

Review 2

Review of the manuscript "A near-term quantum algorithm for solving linear systems of equations based on the Woodbury identity"

Summary

The manuscript presents a novel quantum algorithm aimed at solving linear systems of equations by leveraging the Woodbury matrix identity. The proposed approach seeks to reconcile some of the limitations of existing quantum algorithms such as the Harrow-Hassidim-Lloyd (HHL) algorithm and variational approaches by focusing on simpler quantum routines suitable for near-term quantum hardware. The authors claim that their algorithm avoids the complexities and optimization issues of previous methods while demonstrating significant computational capabilities on current quantum devices.

Main Review Points

1. Innovativeness and Contribution:
2. Strengths: The work is noteworthy for introducing a novel approach that simplifies quantum linear systems algorithms, emphasizing the potential for near-term quantum computing applications. The use of the Woodbury identity to handle low-rank modifications in an easily invertible matrix is substantive, offering a practical solution to a subset of linear systems problems.

3. Limitations: The applicability of the algorithm is inherently limited to cases where the Woodbury identity is suitable, i.e., when dealing with low-rank modifications. This may restrict the broader applicability of the approach in various practical problems.

4. Theoretical Foundation:

5. Strengths: The manuscript is well-anchored in solid mathematical principles, coupling the Woodbury identity with quantum computational techniques effectively. The adapted use of inner product estimation through the Hadamard test demonstrates a clear link between classical numerical methods and quantum computing.

6. Suggestions for Improvement: The condition number analysis in Appendix B is noted to be partially conjectural. It would greatly enhance the manuscript's robustness if the conjecture could be either proven or supported by additional empirical data.

7. Practicality and Feasibility:

8. Strengths: Demonstrating the algorithm’s performance on IBM’s Auckland quantum computer is a significant achievement, notably solving linear systems with up to (2^{24}) equations to a 2% error rate using noise mitigation techniques.

9. Drawbacks: While the zero-noise extrapolation improved results substantially, detailed error analysis and the impact of different hardware noise levels should be discussed further to provide a more comprehensive picture of practical implementations.

10. Computational Cost and Efficiency:

11. The manuscript effectively discusses the computational cost in terms of both classical and quantum operations, emphasizing scenarios where the quantum approach may offer significant advantages. However, it should further elaborate on the specific quantum circuits' depth and gate complexity in various cases, offering comparative analytics with classical counterparts in more detail.

12. Clarity and Presentation:

13. Strengths: The writing is generally clear, and the mathematical derivations are laid out logically. The inclusion of example problems and the use of Qiskit for implementation enhance the manuscript's accessibility.
14. Suggestions for Improvement: There are some sections where clarity could be improved, particularly for readers who may not be deeply familiar with the nuances of quantum computing. Simplifying or elaborating on certain explanations could broaden the manuscript’s accessibility.

Specific Minor Comments

• The introduction provides a solid background but could briefly touch on the broader context of quantum algorithms for linear systems. Mentioning other near-term approaches would add depth.
• In the Results section, the choice of (10^5) shots for inner product estimation seems somewhat arbitrary; a justification based on error bounds or prior benchmarks would add rigor.
• The discussion on potential quantum advantage over classical methods is insightful but would benefit from more concrete examples or hypothetical scenarios where the quantum approach definitively outperforms classical techniques.

Conclusion

The manuscript makes a significant contribution to quantum computing literature by presenting a practical approach tailored for near-term quantum devices while being grounded in established numerical methods. Addressing the minor issues mentioned and providing a deeper error analysis and complexity discussion would further strengthen the manuscript. The work is publishable and should be of great interest to researchers in numerical linear algebra and quantum computing.