Assessment of Quantum Annealing for the Construction of Satisfiability Filters

Dear Editor,

We are grateful for the hard work the referees have spent on improving our manuscript. We will go through their suggestions and detail our changes. Furthermore, we changed the layout of the manuscript to the SciPost style guide.

We changed all typos, broken references (mainly to equations) and grammar issues mentioned by the referees. In the following, we want to address the remaining comments.

Referee Comment:
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.

Response:
This is a valid concern, however we want to test the behavior of QA for SAT problems. The fact that this algorithm finds less separate solutions compared to SA should be independent of system size.
Furthermore, the simulations for quantum annealing are very demanding. We already went to the largest possible size that could be run on our supercomputer. The classical annealing code could have been run much faster but the main idea of the paper is to compare the two algorithms. Thus, our quantum annealing simulation restricts the size of problems.

Referee Comment:
2. The results of [37] 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.

Response:
We agree and added a section to the introduction:
“
The D-Wave quantum annealer has already been used for the creation of SAT filters. However, the chimera-graph of the D-Wave device does not allow arbitrary connections and thus restricts the types of problems, that can be implemented without embedding.
This paper investigates the question whether QA on an arbitrary connected and completely coherent device, can be advantageous for the creation of SAT filters.
”

Referee Comments:
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?

Response:
This sentence in comment 5 was not clearly formulated. Changing this an example for the value of $k$ is now given:
“
Weaver et al.~showed that SAT filters can approach the information theoretical limit ($\mathcal{E}=1$) by increasing the size of its clauses. This also increases the complexity of the problem, but it was shown that even for relatively small values of $k=3$ better performance compared to the constant efficiency of Bloom filters ($\mathcal{E}\leq \ln(2)$) can be achieved.
”
The typical value of $m$ is linked to the number of elements in the set $Y$ from which the filter is created. This has been mentioned several times throughout the paper (see beginning of Section II C or Section II D at the definition of the efficiency)

Referee comment:
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.

Response:
This is an inconsistency: the inverse temperature should be used throughout the paper. We replaced $T_1$ and $T_2$ by their inverse temperatures $\beta_0$ and $\beta_1$. These were already defined at the beginning of Section III.

Referee comment:
7 - Expand on the possible ways forward, as suggested by some of the comments in the report.

Response:
From the well documented report we made changes throughout the paper ensuring that we do not overstate any claims.
We added the limitations of our study already to the introduction:

“Thus, our simulations indicate that QA shows no improvement for the construction of SAT filters. However, it should be noted that nonlinear schedules or non-stoquastic driver Hamiltonians could still improve QA. Such research is left for further work.”

We also rewrote parts of the conclusion and added a new paragraph stating that outlines further possible research:

“The previously mentioned nonlinear schedules and non-stoquastic driver Hamiltonians could improve the performance considerably and should be investigated in further research. This research would not only be important for analog devices such as the D-Wave; but would also be fairly indicative of QA run on a digital quantum computer, where the implementation of more complex driving Hamiltonians should be easier.”

This should address several comments made in the report section of the referee.

Referee comment:
- 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.

Response:
Our analysis shows, that a mixing of SQA and other algorithms does not give any improvements. This has been explained at the end of Seciton IV B (relating to Figure 5).

Referee comment:
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.

Response:
The main focus of this paper is the efficacy of Quantum Annealing. Among other papers, this should give insights into which problems are susceptible to speedup, using quantum annealers such as the D-Wave machine.
Thus, we are of the opinion that this paper is very relevant for physicists and we see no problem for it to be published in a physics journal.

We want to thank the referees again for all the helpful comments and believe that these improved the manuscript considerably.