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 current version.

Submission summary

As Contributors: Wen Wei Ho
Arxiv Link:
Date submitted: 2018-11-06
Submitted by: Ho, Wen Wei
Submitted to: SciPost Physics
Domain(s): Theor. & Comp.
Subject area: Quantum Physics


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 (i) the Greenberger-Horne-Zeilinger (GHZ) state, (ii) a quantum critical state, and (iii) a topologically ordered state, all with perfect fidelity and time that scales as $O(L)$, where $L$ is the linear dimension of the system. 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.

Current status:
Has been resubmitted

Ontology / Topics

See full Ontology or Topics database.

Ising model Quantum simulation Topological quantum computation

Reports on this Submission

Anonymous Report 1 on 2018-12-20 Invited Report


1. Novel and interesting application(s) of the quantum approximate optimization algorithm (QAOA) framework.

2. The paper is well-written and the results and examples are presented in a clean, clear and understandable manner.

3. The main ideas of the paper are demonstrated with examples accessible to a relatively broad audience.


1. The implementation costs resulting from the constructions of this paper - and subsequently any advantages or disadvantages of the constructions - is unclear. The scaling of the total time (sum of the algorithm parameters) is emphasized in the paper; however, a more important quantity, the scaling of the quantum circuit depth (which scales with the number of QAOA$_p$ repetitions p) is underemphasized and underexplored. While closely related, these quantities are not identical, and how these two quantities relate is not explained in the paper.

This point is elaborated on in the Requested Changes section

2. Similarly, "various quantum circuits" are mentioned as alternatives to the applications considered in this paper, yet the implementation costs are not compared in detail nor other (dis)advantages presented.
(An example of such a circuit is given in App. B.)

[For example, comparing the "total time" of two quantum gate-model algorithms is typically not meaningful, whereas metrics such as circuit depth, are.]


The paper "Efficient preparation of non-trivial quantum states using the Quantum Approximate Optimization Algorithm" shows a novel application of QAOA to preparing quantum states, including several provided examples taken from quantum physics.

The results of this paper are of scientific significance as they relate to potential impactful uses of quantum computers. Moreover, quantum state preparation is an important paradigm in quantum computing, generally, with many applications beyond those of this paper.

The paper is generally well-written and the ideas and results are presented clearly.

Hence, modulo a few minor comments below, I am happy to recommend acceptance of this paper for publication.

Requested changes

1. In the abstract, it is stated that the time scales as $O(L)$. It is not clear what "time" means here without some context; c.f. the related comments in this report.
1'. Is $O(L)$ what you mean here? - this implies linear or $sub-linear$ scaling - perhaps replace with $\Theta(L)$ or the phrase "scales linearly".

1. The title of section 3 is "Quantum Approximate Adiabatic Algorithm (QAOA)" - this is confusing to the reader and should be either "Quantum Approximate Optimization Algorithm (QAOA)" or "Quantum Approximate Adiabatic Algorithm"

2. For the benefit of the reader, the GHZ state when first defined should be given as a numbered equation.

3. As mentioned, the paper would benefit from clarification of the relation of the stated results (such as total time) to the circuit complexity (i.e., implementation cost in terms of circuit size and depth) for the given constructions.

Consider for example the GHZ state construction, though the point here applies also to the other constructions of the paper.

The GHZ Hamiltonian (3) can be simulated in many reasonable quantum gate sets with circuit depth that does not depend on $L$, as can be the paramagnetic Hamiltonian. Hence,
(i) the QAOA$_{p=L/2}$ quantum circuit would have circuit depth that scales linearly with $L$, independently of the particular algorithm parameters $\gamma,\beta$.
The authors then find empirically that
(ii) the total time T to achieve perfect fidelity also scales linearly with $L$.
Without an explanation otherwise, facts (i) and (ii) appear to be unrelated. Fact (ii) is reported in the abstract, while fact (i) is often more significant.

Indeed, alternative algorithms for preparing this state may not have well-defined "total times" for comparison to the approach of this paper, and quantum circuit depth is typically a more fruitful metric.

  • validity: high
  • significance: good
  • originality: high
  • clarity: high
  • formatting: excellent
  • grammar: excellent

Author Wen Wei Ho on 2019-01-07
(in reply to Report 1 on 2018-12-20)

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

Anonymous on 2019-01-26
(in reply to Wen Wei Ho on 2019-01-07)

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"...).

Login to report or comment