SciPost Submission Page
Assessment of Quantum Annealing for the Construction of Satisfiability Filters
by Marlon Azinović, Daniel Herr, Ethan Brown, Matthias Troyer
This is not the latest submitted version.
This Submission thread is now published as
|Authors (as registered SciPost users):||Daniel Herr|
|Preprint Link:||http://arxiv.org/abs/1607.03329v3 (pdf)|
|Date submitted:||2016-09-28 02:00|
|Submitted by:||Herr, Daniel|
|Submitted to:||SciPost Physics|
Satisfiability filters, introduced by S. A. Weaver et al. in 2014, are a new and promising type of filters to address set membership testing. In order to construct satisfiability filters, it is necessary to find disparate solutions to hard random $k$-SAT problems. This paper compares simulated annealing, simulated quantum annealing and walkSAT, an open-source SAT solver, in terms of their ability to find such solutions. The results indicate that solutions found by simulated quantum annealing are generally less disparate than solutions found by the other solvers and therefore less useful for the construction of satisfiability filters.
Submission & Refereeing History
You are currently on this page
- Report 2 submitted on 2016-12-07 07:45 by Anonymous
- Report 1 submitted on 2016-11-21 15:42 by Anonymous
Reports on this Submission
- Cite as: Anonymous, Report on arXiv:1607.03329v3, delivered 2016-12-07, doi: 10.21468/SciPost.Report.47
1 - Addresses an problem of interest, with significant practical importance.
2 - Thorough analysis of results obtained.
3 - Solid exposition.
4 - Good description of possible future directions.
1 - Conclusions are too strongly stated, and could discourage future research that might be of value.
2 - Little physics content.
3 - Needs a little more attention to communicating computer science content to physicists who may not be as familiar with the concepts involved as is assumed.
4 - Some sloppiness that can easily be corrected
This paper compares the performance of three classical algorithms, SQA. SA, and walkSAT, on problems related to the construction of satisfiability filters.
My main concern is that the conclusions are too strong for the study described, and may inhibit further work that could potentially be quite interesting, both by inhibiting researchers in looking further and by inhibiting funders from funding such research. For example, at the end of the second paragraph they say “We conclude that QA does not improve the construction of satisfiability filters.” Such a sweeping statement should not be made unless much stronger results or arguments can be put forward. All such statements should be qualified to make clear the limitations of the study. The reason for such care include
- The authors mention a few times that combining QA with SQA and walkSAT might be a good way forward. This suggests that even if QA alone does not improve the construction of SAT filters, it can potentially improve the construction of SAT filters through complementing another algorithm.
- It is widely recognized that for QA to outperform classical methods, the simplest QA algorithm methods are unlikely to suffice. Interest in non-stoquastic Hamiltonians is high, and nothing in this paper suggests that such approaches should not be investigated for potential use in sat filter construction.
- Only a linear QA schedule was used. Such a schedule corresponds to neither the most physically implementable schedule (for example, D-Wave quantum annealers do not use such a schedule) nor the theoretically optimal schedule (theoretical work suggests flatter curves at the beginning and end of the anneal perform better).
- Only a single schedule was used. Multiple schedules could increase the diversity. Beyond varying the schedule for the driver and problem Hamiltonians, past work has shown the efficacy of adding other terms to the Hamiltonian that are zero at both ends, but affect the dynamics in between.
- The classical SQA was used instead of actual QA. While there is strong theoretical work showing that the SQA can be useful in predicting QA performance, the extent to which that analogy holds is unclear, especially for something as little studied as the diversity of solutions.
- Only 20 instances for each k were considered, and these instances did not come from SAT filter application problems, but were instead randomly generated problems at the satisfiability threshold. It is unclear how representative these instances are of the type of instances that will arise in practice.
- QA has two aspects, one as a hardware prescription, the other as a quantum algorithm. The authors comment in their conclusions that this studying is the best case scenario for QA in that any physical QA device would have connectivity restrictions. That is true for near-term quantum annealers, but the QA algorithm is of independent interest – if an idealized version is effective, it can be digitized and run on a universal quantum computer thereby supporting arbitrary connectivity. Thus, quantum annealing as an algorithm could be useful for this problem even if it turns out quantum annealers are not.
The paper is a solid study, but the authors should go through the paper carefully, and modify any statements that overstate their conclusions (there are others than the example given above).
A secondary concern is that this paper has been submitted to SciPost Physics, but contains very little physics content. Sure, simulated annealing is a computer science algorithm inspired by classical physics and SQA is a computer science algorithm inspired by quantum physics, but there is essentially no discussion of physics. This paper appears to this reviewer to be a pure computer science paper, albeit one that will be of interest to the quantum computing community. The authors should consider whether insights from physics can be helpful in illuminating the results. The editorial board should consider whether pure computer science papers are appropriate for this new journal.
1 - Used dashed lines, etc., in the figures so they are more easily readable when the paper is printed in b/w/
2 - Fix broken references, currently appearing as ??, throughout the paper, particularly for Equations.
3 - Sentence near bottom of right hand column of p.2 should read "If none of the stored solutions satisfy the newly ..."
4 - What are the typical values of k and m. (Generally, a little more grounding of SAT fliters would be helpful to a physics audience.)
5 - Clarify what is meant by "theoretically" in the sentence "Weaver et al. showed that SAT filters can theoretically achieve the limit ..." Does this mean a non-constructive proof was given but no actual construction is known, or known constructions are too computationally expensive, or something else entirely?
6 - At the beginning of section III.C., T_0 and T_1 are mentioned, but these have not been introduced earlier. The reader can guess that they are the initial and final temperature, but this should be spelled out.
It is inaccurate to say that the number of solutions found has saturated by 2000 runs in Fig. 1. The slope is still quite positive at the endpoint.
7 - Expand on the possible ways forward, as suggested by some of the comments in the report.
- Cite as: Anonymous, Report on arXiv:1607.03329v3, delivered 2016-11-21, doi: 10.21468/SciPost.Report.40
I have a strong background in Satisfiability, but not much knowledge of Quantum Physics. So, I decline to provide comments on Section III.
1. The connection between these new filters and quantum physics is really cool.
2. The paper explores in depth the original SAT filter type (clauses), something  glossed over.
1. For SAT filters to be practical, larger instances need to be solved. This paper only considers instances with 50 variables, allowing for filters with ~400 elements. Practical filters should be able to have millions of elements, something not discussed, and only barely hinted at in the conclusions. I would like to _also_ see results with more variables, at least to get a sense of scale.
I do appreciate the appendix results for k=3 and k=5
2. The results of  should be addressed more fully. Use the introduction (or a background section) to explain how you differ. Instead, this was minimally discussed in the Conclusions section.
The paper was enjoyable to read. The topic is very interesting and addresses the open problem of finding disparate solutions to random k-SAT instances. Though the paper focuses on instances coming from the domain of SAT filters, the results are relevant even removed from the domain. See Moshe Vardi's recent work on methods for finding uniform solutions to SAT instances --- http://www.cs.rice.edu/~vardi/papers/cav16tk.pdf
1. Abstract --- walkSAT should be WalkSAT
2. define SAT
3. "promising type of filters" -> "promising type of filter"
4. Introduction --- boolean should always be Boolean
5. "boolean satisfiability problems" -> "Boolean satisfiability problem"
6. "find solutions, which are" -> "find solutions which are"
7. Satisfiability filters --- "It can be queried..." What is "It"?
8. "the appearing variables, is" -> "the appearing variables is"
9. "ki in Equation ??" What is "??"
10. "the solvability of a random..." Solvability is not the right word. The right word is Satisfiability.
11. "is chosen, which map" -> "is chosen which map"
12. Another "Equation ??"
13. Another "Equation ??"
14. "to a clause that is fulfilled" Please stop using a thesaurus to find other ways to say Satisfied. Just say satisfied.
15. "and a FPR p, is defined " The correct reference is , not .
16. Results and Discussion --- "see section II B" -> Section should be uppercase