SciPost Submission Page
Efficient preparation of non-trivial quantum states using the Quantum Approximate Optimization Algorithm
by Wen Wei Ho, Timothy H. Hsieh
This is not the latest submitted version.
This Submission thread is now published as
Submission summary
| Authors (as registered SciPost users): | Wen Wei Ho |
| Submission information | |
|---|---|
| Preprint Link: | https://arxiv.org/abs/1803.00026v3 (pdf) |
| Date submitted: | 2019-01-18 01:00 |
| Submitted by: | Ho, Wen Wei |
| Submitted to: | SciPost Physics |
| Ontological classification | |
|---|---|
| Academic field: | Physics |
| Specialties: |
|
| Approaches: | Theoretical, Computational |
Abstract
We provide an efficient and general route for preparing non-trivial quantum states that are not adiabatically connected to unentangled product states. Our approach is a variant of the 'Quantum Approximate Optimization Algorithm' (QAOA) [E. Farhi et al., arXiv:1411.4028] and is experimentally realizable on near-term quantum simulators of synthetic quantum systems. As proof of concept, our approach yields explicit protocols which prepare with perfect fidelities (i) the Greenberger-Horne-Zeilinger (GHZ) state, (ii) a quantum critical state, and (iii) a topologically ordered state, all with $p = L/2$ iterations of the algorithm and physical runtimes $T$ that scale linearly with the system size $L$, i.e. $T \sim L$. The protocol is additionally able to prepare the ground states of antiferromagnetic Heisenberg chains with very good fidelities. Besides being practically useful, our results also illustrate the utility of QAOA-type circuits as variational wavefunctions for non-trivial states of matter.
Author comments upon resubmission
With this reply letter, we would like to submit a revised version of our manuscript "Efficient preparation of non-trivial quantum states using the Quantum Approximate Optimization Algorithm" for your consideration for publication in SciPost. We thank you for arranging the review of our manuscript.
We thank the Referee once again for the careful consideration, and also for the insightful comments which helped improve our work. We are happy to learn of the Referee's appreciation of the impact of our work ("novel and interesting applications", "accessible to a relatively broad audience"), and also of the recommendation of acceptance of the paper to SciPost.
In the revised version of the manuscript, we have effected all of the changes requested by the Referee and as detailed in our Reply previously. In particular, we have added a discussion in Sec 3 regarding the relation between the QAOA iteration depth p and the total runtime t of the algorithm, and explained why the latter is the more meaningful of the two metrics in terms of implementation costs. In doing so, we believe we have adequately addressed the Referee's main comment that the 'circuit depth' of the QAOA is the more fruitful metric; we humbly disagree with this point. In a nutshell (and as elaborated upon in our previous reply to the Refereee), as the QAOA is envisioned to be run on noisy near-term analog quantum simulators, the total runtime to implement the algorithm (relative to the noise) is an important metric to gauge its success. We emphasize that the QAOA is not a digital quantum circuit comprised of gates from a fixed gate set, and thus, it can be misleading to view the QAOA iteration number p as equivalent to the depth of some quantum circuit. We thank the Referee for bringing up this potentially confusing point though, and we believe the changes we have made will have clarified this issue sufficiently.
We hope that with these changes, our improved manuscript will now meet the high standards for publication in SciPost. Thank you for your consideration, and please let us know if any additional information or material could be useful.
Sincerely,
Authors
List of changes
1. With respect to the Refere's comment that the statement regarding scaling of the time with system size is not clear in the abstract -- we have accordingly modified the abstract to explicitly report both that (i) the number of QAOA iterations to achieve perfect fidelity is p = L/2 and that (ii) the minimum physical runtimes T needed, scales linearly as T ~ L.
2. With regards to the title of Section 3 -- this is indeed a typo and we have corrected it to "Quantum Approximate Optimization Algorithm".
3. As per the Refere's suggestion, we have given the GHZ state as a numbered equation [Eq. (1) in the revised version] when first defining it.
4. With regards to clarification on the two metrics of the implementation costs -- the QAOA iterations p and the total runtime t -- as argued both in our initial Reply to the Referee and in the Reply letter accompanying the resubmission, we believe the total physical runtime t is actually the more meaningful metric (relative to the noise of a near-term quantum simulator), in contrary to the Referee's comments. We also believe that it is misleading to view the iteration depth p as the depth of a digital quantum circuit, as the QAOA is not the latter -- the QAOA explicitly depends on analog parameters $\beta_i, \gamma_i$ which are the runtimes to implement each layer $H_I, H_X$.
We have sought to clarify these points better through a number of changes in the revised manuscript:
i) We have removed references to 'p' as the 'depth' of the QAOA protocol, to prevent misunderstanding of this parameter as the depth of a quantum circuit (it is not). Instead, we call it the number of iterations of the QAOA protocol.
ii) As per the Referee's request, we have added a discussion in Sec 3 regarding the relation of the two metrics p and total runtime t, and explained why t is the more meaningful quantity in light of the QAOA being envisioned to be run on noisy, intermediate, analog quantum simulators. We have also emphasized how the QAOA is not a digital quantum circuit, and provided a reference [Quantum 2, 79 (2018)] elucidating the difference.
iii) In the examples of target states studied, we have made explicit the separate points which we found numerically--as noted by the Referee, that (a) the target states studied can be prepared perfectly at p = L/2 (which implies that the total physical runtimes t = O(L) as the angles are bounded from above); and (b) that the Minimum total runtimes T are found to scale linearly with L.
iv) Related to point iii) above, we have been careful to refer to t as the runtime of a given QAOA protocol (of some fixed p), and T as the {\it minimum} runtimes of over all such t's. Equations defining t and T are given in the main text.
Current status:
Reports on this Submission
Report #1 by Anonymous (Referee 1) on 2019-1-27 (Invited Report)
- Cite as: Anonymous, Report on arXiv:1803.00026v3, delivered 2019-01-26, doi: 10.21468/SciPost.Report.804
Strengths
See previous report.
Weaknesses
See previous report.
Report
There seems to be much confusion regarding the remarks contained in my initial review.
This reviewer is perplexed by the author's overly confident response to an initially minor comment regarding the paper.
Unfortunately the related sections of the text require further revision before I can recommend the paper for publication.
Fortunately this change is relatively minor and I see no reason to delay acceptance of the paper assuming a reasonable fix is proposed.
I advise the authors to review the literature. I give a few examples below.
Note that the authors have separately provided a confusing response to my initial review of the paper. I have provided an additional response, in context, attached to the same comment thread - please see the associated webforms.
Some of my same points will be repeated below.
I have further pasted my response at the bottom of this text.
=====
Some further specific comments regarding the paper revision:
- In the revised abstract, it is not explained what the parameter p is
-As the QAOA time parameters are each bounded by a small constant, the total time is bounded by a constant times the QAOA circuit depth p. The authors appear to have made statements both agreeing with and contradicting this statement.
- Regarding the revisions to section 3:
The authors' insistence that QAOA should be seen as an analog algorithm (only) is inexplicable.
This contradicts the literature, where it is presented as a digital quantum algorithm;
see e.g.:
[Farhi14] A quantum approximate optimization algorithm. E Farhi, J Goldstone, S Gutmann arXiv:1411.4028, 2014.
[Farhi17] Quantum algorithms for fixed qubit architectures. E Farhi, J Goldstone, S Gutmann, H Neven arXiv:1703.06199, 2017
[Had18] Quantum Algorithms for Scientific Computing and Approximate Optimization S Hadfield arXiv:1805.03265, 2018
[Lech18] Quantum Approximate Optimization with Parallelizable Gates
W Lechner arXiv:1802.01157, 2018
[Ventu18] Compiling quantum circuits to realistic hardware architectures using temporal planners D Venturelli, M Do, E Rieffel J Frank Quantum Science and Technology, 2018 Feb 21;3(2):025004.
-The authors write "We note here that it is tempting to view the number of iterations p of the QAOA protocol as the ‘depth’ of a quantum circuit and relate that to its ‘complexity’."
This is inconsistent with the computer science literature. Notions of algorithm complexity and gate depth are standard and important notions in both classical and quantum circuit complexity. The whole point of circuit depth is that it gives an *architecture independent* metric, an \textit{invariant}, which allows for algorithm evaluation.
Consider, for example, the original proposed implementation of QAOA for the MaxCut problem in [Farhi14].
The initial state can be prepared in depth 1 using Hadamard gates.
The mixing operator can be applied in depth 1 using X rotation gates.
The phase operator can be applied in depth proportional to the maximum graph degree using ZZ-rotations.
So in this case the gate depth follows directly from the QAOA circuit depth.
Nevertheless, at the level of compilation to primitive quantum gates, different architectures may require additional auxiliary interactions (e.g., swap gates to interact distant qubits, or non-clifford gates in fault tolerant settings), so the cost implementing of the QAOA operators with bounded angles is often bounded by a constant.
In different quantum algorithm such as e.g. Hamiltonian simulation the time parameter is not bounded by a constant and becomes an input complexity parameter, but this is not the case here.
=====
Response to the authors' comments on the initial review of their paper:
=====
Once again I cannot agree with the authors, and I am, quite frankly, surprised by their insistence.
Their statements appear to reflect personal opinion rather than the literature.
The authors correctly state that the total time and QAOA circuit depth are "closely related" quantities and that each angle is "uniformly upper bounded by some constant".
However, in the next paragraph, they refer to the same angles as "analog parameters..which can be small or large."
This is inconsistent with the previous statement.
Please refer to how small constants are treated in the computer science literature on algorithms.
The authors state that "the QAOA algorithm is not a 'digital' quant circuit..where gates from a fixed set".
This is not true, as clearly is clearly evidenced by the literature.
See e.g.:
[Farhi14] A quantum approximate optimization algorithm. E Farhi, J Goldstone, S Gutmann arXiv:1411.4028, 2014.
[Farhi17] Quantum algorithms for fixed qubit architectures. E Farhi, J Goldstone, S Gutmann, H Neven arXiv:1703.06199, 2017
[Had18] Quantum Algorithms for Scientific Computing and Approximate Optimization
S Hadfield arXiv:1805.03265, 2018
[Lech18] Quantum Approximate Optimization with Parallelizable Gates
W Lechner arXiv:1802.01157, 2018
[Ventu18] Compiling quantum circuits to realistic hardware architectures using temporal planners
D Venturelli, M Do, E Rieffel J Frank Quantum Science and Technology, 2018 Feb 21;3(2):025004.
Cost invariants such as circuit depth are standard in the computer science literature, for good reason, and should not be treated lightly. They provide a largely implementation-independent measure of an algorithm's cost.
If the authors wish to limit their results to "analog" platforms, that is at their loss. For digital quantum platforms, including those emerging from Google, Rigetti, etc., other factors such as connectivity are important and greatly affect the compiled low-level gate cost. Moreover, for other proposals such as fault-tolerant quantum computing schemes, the critical resource may be the number of non-clifford gates, which one expects to scale with circuit depth.
QAOA has been considered for all of these platforms, as well as for non-near-term devices;
see e.g.
[Farhi16] Quantum supremacy through the quantum approximate optimization algorithm
E Farhi, AW Harrow arXiv:1602.07674, 2016
[Jia17] Near-optimal quantum circuit for Grover's unstructured search using a transverse field
Z Jiang, EG Rieffel, Z Wang PRA, 2017
With regards to the author's paragraph "As a concrete example...", again, I cannot agree. Quantum gate model algorithms are fundamentally distinct as computational models from continuous time algorithms like the quantum adiabatic optimization; please consult the literature.
Moreover, for a gate-model algorithm such as QAOA, which is typically repeated many times in a hybrid classical loop and generates outputs probabilistically, it is not clear how noise will affect the performance of the algorithm (in contrast , e.g., to an algorithm such as Shor's where one might imagine the intermediate and final states to be much more "delicate"...).
Requested changes
See the above report.