Pei Yuan

The QAOA has been the subject of intense study over recent years, yet the corresponding Dynamical Lie Algebra (DLA)--a key indicator of the expressivity and trainability of VQAs--remains poorly understood beyond highly symmetric instances. An exponentially scaling DLA dimension is associated with the presence of so-called barren plateaus (BP) in the optimization landscape, which renders training intractable. In this work, we investigate the DLA of QAOA applied to the canonical MaxCut, for both weighted and unweighted graphs. For weighted graphs, we show that when the weights are drawn from a continuous distribution, the DLA dimension grows as $Θ(4^n)$ almost surely for all connected graphs except paths and cycles. In the more common unweighted setting, we show that asymptotically all but an exponentially vanishing fraction of graphs have $Θ(4^n)$ large DLA dimension. The entire simple Lie algebra decomposition of the corresponding DLAs is also identified, from which we prove that the variance of the loss function is $O(1/2^n)$, implying that QAOA on these weighted and unweighted graphs all suffers from BP. Moreover, we give explicit constructions for families of graphs whose DLAs have exponential dimension, including cases whose MaxCut is in $\mathsf P$. Our proof of the unweighted case is based on a number of splitting lemmas and DLA-freeness conditions that allow one to convert prohibitively complicated Lie algebraic problems into amenable graph theoretic problems. These form the basis for a new algorithm that computes such DLAs orders of magnitude faster than previous methods, reducing runtimes from days to seconds on standard hardware. We apply this algorithm to MQLib, a classical MaxCut benchmark suite covering over 3,500 instances with up to 53,130 vertices, and find that, ignoring edge weights, at least 75% of the instances possess a DLA of dimension at least $2^{128}$.

The expressibility and trainability of parameterized quantum circuits has been shown to be intimately related to their associated dynamical Lie algebras (DLAs). From a quantum algorithm design perspective, given a set $A$ of DLA generators, two natural questions arise: (i) what is the DLA $\mathfrak{g}_{A}$ generated by ${A}$; and (ii) how does modifying the generator set lead to changes in the resulting DLA. While the first question has been the subject of significant attention, much less has been done regarding the second. In this work we focus on the second question, and show how modifying ${A}$ can result in a generator set ${A}'$ such that $\mathfrak{g}_{{A}'}\cong \bigoplus_{j=1}^{K}\mathfrak{g}_{A}$, for some $K \ge 1$. In other words, one generates the direct sum of $K$ copies of the original DLA. In particular, we give qubit- and parameter-efficient ways of achieving this, using only $\log K$ additional qubits, and only a constant factor increase in the number of DLA generators. For cyclic DLAs, which include Pauli DLAs and QAOA-MaxCut DLAs as special cases, this can be done with $\log K $ additional qubits and the same number of DLA generators as ${A}$.

The $n$-qubit $k$-weight Dicke states $|D^n_k\rangle$, defined as the uniform superposition of all computational basis states with exactly $k$ qubits in state $|1\rangle$, form a basis of the symmetric subspace and represent an important class of entangled quantum states with broad applications in quantum computing. We propose deterministic quantum circuits for Dicke state preparation under two commonly seen qubit connectivity constraints: 1. All-to-all qubit connectivity: our circuit has depth $O(\log(k)\log(n/k)+k)$, which improves the previous best bound of $O(k\log(n/k))$. 2. Grid qubit connectivity ($(n_1\times n_2)$-grid, $n_1\le n_2$): (a) For $k\ge n_2/n_1$, we design a circuit with depth $O(k\log(n/k)+n_2)$, surpassing the prior $O(\sqrt{nk})$ bound. (b) For $k< n_2/n_1$, we design an optimal-depth circuit with depth $O(n_2)$. Furthermore, we establish the depth lower bounds of $Ω(\log(n))$ for all-to-all qubit connectivity and $Ω(n_2)$ for $(n_1\times n_2)$-grid connectivity constraints, demonstrating the near-optimality of our constructions.

Some physical implementation schemes of quantum computing can apply two-qubit gates only on certain pairs of qubits. These connectivity constraints are commonly viewed as a significant disadvantage. For example, compiling an unrestricted $n$-qubit quantum circuit to one with poor qubit connectivity, such as a 1D chain, usually results in a blowup of depth by $O(n^2)$ and size by $O(n)$. It is appealing to conjecture that this overhead is unavoidable -- a random circuit on $n$ qubits has $\Theta(n)$ two-qubit gates in each layer and a constant fraction of them act on qubits separated by distance $\Theta(n)$. While it is known that almost all $n$-qubit unitary operations need quantum circuits of $\Omega(4^n/n)$ depth and $\Omega(4^n)$ size to realize with all-to-all qubit connectivity, in this paper, we show that all $n$-qubit unitary operations can be implemented by quantum circuits of $O(4^n/n)$ depth and $O(4^n)$ size even under {1D chain} qubit connectivity constraint. We extend this result and investigate qubit connectivity in three directions. First, we consider more general connectivity graphs and show that the circuit size can always be made $O(4^n)$ as long as the graph is connected. For circuit depth, we study $d$-dimensional grids, complete $d$-ary trees and expander graphs, and show results similar to the 1D chain. Second, we consider the case when ancillary qubits are available. We show that, with ancilla, the circuit depth can be made polynomial, and the space-depth trade-off is not impaired by connectivity constraints unless we have exponentially many ancillary qubits. Third, we obtain nearly optimal results on special families of unitaries, including diagonal unitaries, 2-by-2 block diagonal unitaries, and Quantum State Preparation (QSP) unitaries, the last being a fundamental task used in many quantum algorithms for machine learning and linear algebra.

As a cornerstone for many quantum linear algebraic and quantum machine learning algorithms, controlled quantum state preparation (CQSP) aims to provide the transformation of $|i\rangle |0^n\rangle \to |i\rangle |\psi_i\rangle $ for all $i\in \{0,1\}^k$ for the given $n$-qubit states $|\psi_i\rangle$. In this paper, we construct a quantum circuit for implementing CQSP, with depth $O\left(n+k+\frac{2^{n+k}}{n+k+m}\right)$ and size $O\left(2^{n+k}\right)$ for any given number $m$ of ancillary qubits. These bounds, which can also be viewed as a time-space tradeoff for the transformation, are \optimal for any integer parameters $m,k\ge 0$ and $n\ge 1$. When $k=0$, the problem becomes the canonical quantum state preparation (QSP) problem with ancillary qubits, which asks for efficient implementations of the transformation $|0^n\rangle|0^m\rangle \to |\psi\rangle |0^m\rangle$. This problem has many applications with many investigations, yet its circuit complexity remains open. Our construction completely solves this problem, pinning down its depth complexity to $\Theta(n+2^{n}/(n+m))$ and its size complexity to $\Theta(2^{n})$ for any $m$. Another fundamental problem, unitary synthesis, asks to implement a general $n$-qubit unitary by a quantum circuit. Previous work shows a lower bound of $\Omega(n+4^n/(n+m))$ and an upper bound of $O(n2^n)$ for $m=\Omega(2^n/n)$ ancillary qubits. In this paper, we quadratically shrink this gap by presenting a quantum circuit of the depth of $O\left(n2^{n/2}+\frac{n^{1/2}2^{3n/2}}{m^{1/2}}\right)$.

As a cornerstone for many quantum linear algebraic and quantum machine learning algorithms, controlled quantum state preparation (CQSP) aims to provide the transformation of |i&#x27E9;|0n&#x27E9;&#x2192;|i&#x27E9;|&#x03C8;i&#x27E9; for all i&#x2208;{0,1}k for the given n-qubit states |&#x03C8;i&#x27E9;. In this paper, we construct a quantum circuit for implementing CQSP, with depth O(n+k+2n+kn+k+m) and size O(2n+k) for any given number m of ancillary qubits. These bounds, which can also be viewed as a time-space tradeoff for the transformation, are optimal for any integer parameters m,k&#x2265;0 and n&#x2265;1. When k=0, the problem becomes the canonical quantum state preparation (QSP) problem with ancillary qubits, which asks for efficient implementations of the transformation |0n&#x27E9;|0m&#x27E9;&#x2192;|&#x03C8;&#x27E9;|0m&#x27E9;. This problem has many applications with many investigations, yet its circuit complexity remains open. Our construction completely solves this problem, pinning down its depth complexity to &#x0398;(n+2n/(n+m)) and its size complexity to &#x0398;(2n) for any m. Another fundamental problem, unitary synthesis, asks to implement a general n-qubit unitary by a quantum circuit. Previous work shows a lower bound of &#x03A9;(n+4n/(n+m)) and an upper bound of O(n2n) for m=&#x03A9;(2n/n) ancillary qubits. In this paper, we quadratically shrink this gap by presenting a quantum circuit of the depth of O(n2n/2+n1/223n/2m1/2&#xA0;&#xA0;).

The Quantum State Preparation problem aims to prepare an $n$-qubit quantum state $|\psi_v\rangle =\sum_{k=0}^{2^n-1}v_k|k\rangle$ from the initial state $|0\rangle^{\otimes n}$, for a given unit vector $v=(v_0,v_1,v_2,\ldots,v_{2^n-1})^T\in \mathbb{C}^{2^n}$ with $\|v\|_2 = 1$. The problem is of fundamental importance in quantum algorithm design, Hamiltonian simulation and quantum machine learning, yet its circuit depth and size complexity remain open when ancillary qubits are available. In this paper, we study efficient constructions of quantum circuits with $m$ ancillary qubits that can prepare $|\psi_v\rangle$ in depth $\tilde O\left(\frac{2^n}{m+n}+n\right)$and size $O(2^n)$, achieving the optimal value for both measures simultaneously. These results also imply a depth complexity of $\Theta(4^n/(m+n))$ for quantum circuits implementing a general $n$-qubit unitary using $m = O(2^n/n)$ ancillary qubits. This resolves the depth complexity for circuits without ancillary qubits, and for circuits with exponentially many ancillary qubits, this gives a quadratic saving from $O(4^n)$ to $\tilde \Theta(2^n)$. Our circuits are deterministic, prepare the state and carry out the unitary precisely, utilize the ancillary qubits tightly and the depths are optimal in a wide range of parameter regime. The results can be viewed as (optimal) time-space tradeoff bounds, which is not only theoretically interesting, but also practically relevant in the current trend that the number of qubits starts to take off, by showing a way to use a large number of qubits to compensate the short qubit lifetime.