Efficient preparation of non-trivial quantum states using the Quantum Approximate Optimization Algorithm

We thank the Referee very much for the appreciation of our work, the insightful comments which will help improve our paper, and also for the recommendation for publication in SciPost.

We would like to respond to some of the Referee's main comments:

1) The Referee mentions that a more meaningful quantity than the scaling of the total time $T$ of the algorithm (which is the sum of the total angles $T = \sum_{i=1}^p (\beta_i + \gamma_i)$) is the closely related quantity, the QAOA circuit depth ($p$). We note that we have reported both metrics in the paper: they scale linearly with system size $L$. Indeed, in our paper, at least for the cases studied, the total time is related to the circuit depth as $T=O(1)$ times depth $p$ because each angle $\beta_i,\gamma_i$ are uniformly upper bounded by some constant and are hence $O(1)$ times.

However, we respectfully disagree that the QAOA-depth $p$ is the more meaningful metric. We note that the QAOA algorithm is not a 'digital' quantum circuit, that is, it is not an algorithm where gates from a fixed set (e.g. CNOT, Hadamard, etc) are chosen. Thus, treating the QAOA depth $p$ as the depth of a quantum circuit, the latter of which counts the number of times gates from this fixed set are drawn which determines the algorithm's complexity, can be misleading. This is because each layer of the QAOA iteration depends also on an analog parameter $\gamma_i$ or $\beta_i$ (which have the interpretation of runtimes, and which can be small or large). Since physical near-term quantum simulators have a limitation on how long they can be coherently run for (crudely set by the $T_2$ time), a comparison of the total time $T$ taken for the algorithm to run relative to this coherence time is a meaningful one.

As a concrete example, suppose we have two QAOA 'circuits' of similar depth $p$. In one case, say all angles $\beta_i, \gamma_i$s are very close to $0$; while in the other case say the angles are large, $\gg 0$. Then arguably the latter circuit is more 'complex', in the sense that it will accumulate more errors in a physical implementation of the algorithm. (We note that we have provided an analysis of this line of reasoning in the appendix; though this analysis ignores possible imperfections due to 'switching' between Hamiltonians in the implementation). Moreover, we note that the physical runtime is the more meaningful one for comparison with a more conventional algorithm, for example, the quantum adiabatic algorithm (QAA).

With regards to the Referee's example about the GHZ state -- we agree that facts (i) and (ii) raised are distinct, although related. Paraphrased, we find empirically that: (i) The QAOA depth to achieve perfect fidelity of the studied target states is $p = L/2$. (ii) Point (i) does not, however, determine the scaling of the total time (although we can say they are upper bounded by a constant * p, as mentioned above). We furthermore find that the total time scales as $L$. These are indeed two separate points as the Referee mentioned, though for reasons stated above, we believe (ii) to be more physically relevant.

Nevertheless, we appreciate the Referee's critique and have taken the suggestions constructively -- as per the Referee's advice, we will include a discussion similar to the one we have provided here regarding the differences in the two metrics, and to highlight the fact that points (i) and (ii) are distinct, but related, statements, in both the abstract and the main text. We believe this will help clarify the differences between the two metrics which will improve the manuscript.

2) Regarding the requested changes on the title of Section 3 (this was indeed a typo; it should read Quantum Approximation Optimization Algorithm) and the definition of the GHZ state, we will rectify that in the next iteration. We thank the Referee for pointing these out.

We thank the Referee once again for his/her comments. Sincerely, Authors