Hay from the haystack: explicit examples of exponential quantum circuit complexity

In this section, we introduce some fundamental notions and definitions concerning circuit complexity. The quantum circuit complexity of a state or unitary on an $n$-partite Hilbert space quantifies the number of local building blocks that are required for their implementation. The Hilbert space that we will consider is $(\mathbb{C}^{d})^{\otimes n}\simeq\mathbb{C}^{d^{n}}$ for arbitrary $d\in\mathbb{N}$. That is, the local system will be a qu$d$it and the ‘local building blocks’ will be one or two-qudit gates. More specifically, we fix a gate set $\mathcal{G}\subset U(d^{2})$ that is assumed to be universal in the sense that the group it generates is dense in $U(d^{2})$.¹¹1From a physical perspective it suffices to generate a dense subset of the projective unitary group $U(d^{n})/U(1)$. However, we will mostly disregard this quotient since it would make many of the statements more cumbersome without changing their essence. In particular, it would not change the $n$-dependence of the results since a global phase can always be changed locally. This means that for any $U\in U(d^{n})$ and any $\epsilon>0$ there is a finite sequence of unitaries $U_{1},\ldots,U_{g}\in U(d^{n})$ such that

where each $U_{i}$ is up to a permutation of tensor factors of the form $U_{i}\simeq V_{i}\otimes\mathbbm{1}_{d}^{\otimes(n-2)}$ with $V_{i}\in\mathcal{G}$. The smallest number $g$ for which this is possible then defines the quantum circuit complexity $\mathcal{C}_{\epsilon}(U,\mathcal{G})$. We will often consider the entire unitary group $U(d^{2})$ as a gate set and write $\mathcal{C}_{\epsilon}(U):=\mathcal{C}_{\epsilon}(U,U(d^{2}))$. Clearly, $\mathcal{C}_{\epsilon}(U)\leq\mathcal{C}_{\epsilon}(U,\mathcal{G})$ holds for any $\mathcal{G}\subset U(d^{2})$. By the Solovay-Kitaev theorem [KSV02], an inequality in the opposite direction can be proven as well. That is, if an $n$-qudit unitary is hard to approximate with any finite universal gate set, then the same is true with the gate library consisting of all one- and two-qudit gates. This well-known fact is spelled out in the following Lemma for the case of efficiently universal gate sets, i.e., those which enable an $\epsilon$-approximation within $SU(d^{2})$ with $g=O(\ln 1/\epsilon)$. Efficiently universal gate sets with cardinality $|\mathcal{G}|\leq 3(d^{2}-1)$ were constructed in [HRC02].

Remarks: (i) It is unclear how restrictive the assumption is for $\mathcal{G}$ to be efficiently universal, as opposed to merely universal within $SU(d^{2})$. In the latter case, a bound similar to Eq.(2) holds if the logarithm is taken to some power $p$ [Var13]. Depending on assumptions (e.g. whether $\mathcal{G}$ includes inverses) proven bounds for $p$ range from $p=3$ [OSH22] over $p=3.97$ [DN06] to $p=O(\ln d)$ [BGT21]. (ii) The restriction to the special (or projective) unitary group is necessary for the Solovay-Kitaev theorem. However, since a global phase can be changed locally, without additional $n$-dependence, the distinction between $SU(d^{n})$ and $U(d^{n})$ is not relevant for our purpose.

If the entire unitary group $U(d^{2})$ is chosen as gate library, then even in the exact case ($\epsilon=0$) every unitary $U\in U(d^{n})$ has finite circuit complexity $\mathcal{C}_{0}(U)=O(d^{2n})$ [BOB05]. Moreover, since the set $\{V\in U(d^{n})|\;\mathcal{C}_{0}(V)<g\}$ is compact, we have that

Here we can choose any positive $\epsilon<\inf\{\|U-V\|_{\infty}|\;V\in U(d^{n})\wedge\mathcal{C}_{0}(V)<g\}$ since compactness of the variational set together with the continuity of the norm guarantee that the infimum is non-zero.

The definition of the mentioned quantum circuit complexities is easily generalized from unitaries to states: the circuit complexity of a state is defined as the minimum exact circuit complexity of all unitaries that generate the considered state from a product state (up to $\epsilon$). In particular, for a pure state given by a unit vector $|\varphi\rangle\in(\mathbb{C}^{d})^{\otimes n}$:

Similarly, for a density operator $\rho$ acting on $(\mathbb{C}^{d})^{\otimes n}$ we define

Other notions of circuit complexity could be defined by considering ancillas also for the cases of pure states or unitaries and/or by allowing for measurements. However, these can all be bounded from below by the minimal size of the respective tensor network description.

We will employ a perspective on tensors that is targeted on their explicit numerical representation. That is, we will consider tensors represented in a given product basis so that they become multi-dimensional arrays of complex numbers. For simplicity, we assume that each dimension has the same size, say $d$, so that a tensor of order $n$ becomes a map $\Psi:\mathbb{Z}_{d}^{n}\rightarrow\mathbb{C}$, i.e., for any $j=(j_{1},\ldots,j_{n})\in\mathbb{Z}_{d}^{n}$, which specifies a location in the array, $\Psi(j)$ is the corresponding complex number. A unitary $U$ that acts on $(\mathbb{C}^{d})^{\otimes n}$, when represented in a product basis, then becomes a tensor of order $2n$ that maps $\mathbb{Z}_{d}^{n}\times\mathbb{Z}_{d}^{n}\ni(j,k)\mapsto\langle j_{1},\ldots,j_{n}|U|k_{1},\ldots,k_{n}\rangle$.

A tensor network representation of a tensor $\Psi:\mathbb{Z}_{d}^{n}\rightarrow\mathbb{C}$ has two ingredients: a graph and an assignment of tensors to the ‘internal’ vertices of that graph. More precisely, the set $V$ of vertices of the graph is assumed to be a union $V=V_{i}\cup V_{e}$ of $|V_{e}|=n$ ‘external’ (or ‘physical’) vertices that have degree one and ‘internal’ (or ‘virtual’) vertices in $V_{i}$ of higher degree. To each edge $e$ there is assigned a dimension parameter $d_{e}\in\mathbb{N}$, which is constrained to $d_{e}=d$ if the edge connects to an external vertex. In addition, each internal vertex $v\in V_{i}$ gets assigned a tensor $\psi_{v}:\mathbb{Z}_{d_{e_{1}}}\times\cdots\times\mathbb{Z}_{d_{e_{\delta}}}\rightarrow\mathbb{C}$, where the order $\delta$ equals the degree of the vertex and the $e_{i}$’s are the vertex’ edges. Finally, $\Psi$ is represented by the tensor network if it is obtained from the product $\prod_{v\in V_{i}}\psi_{v}$ after contracting (i.e., summing) over all indices that correspond to edges that connect internal vertices.

If $N=|V_{i}|$ is the number of internal vertices, $\delta$ is a uniform upper bound on their degree and $D:=\max_{e}\{d_{e}\}$ defines the ‘maximal bond dimension’, then the number of complex numbers that specify the tensor network is at most

The representation of a unitary $U$ on $(\mathbb{C}^{d})^{\otimes n}$ in terms of a circuit of size $N$ can be regarded as a special case of a tensor network representation with $D=d$ and $N$ internal vertices, each of degree $\delta=4$ (see Fig.1). Similarly, a state vector $|\varphi\rangle\in(\mathbb{C}^{d})^{\otimes n}$ generated from a product $|0\rangle^{\otimes(n+m)}$ via a unitary circuit of size $N$ and conditioned on outcomes of local measurements on an $m$-partite ancilla has a tensor network representation with $|V_{i}|=N$, $D=d$ and $\delta\leq 4$.

In this section we employ a standard counting argument [Kni95, NC02] to quantify hardness of approximation for generic diagonal unitaries. In order to get a countable set, we consider a finite gate library $\mathcal{G}\subset U(d^{2})$. By Lemma 1, however, the derived results can easily be transferred to the case of any other gate set, including infinite ones.

The following theorem makes the statement ‘almost all diagonal unitaries are hard to approximate’ precise, by showing that the set that can be approximated by circuits of sub-exponential size $O(d^{n}/\ln n)$ is double-exponentially small.

Remarks: Note that $\arcsin(\epsilon/2)\simeq\epsilon/2$ up to $O(\epsilon^{3})$. A result closely related to (1) can be found in [Nie06] formulated in terms of geodesic lengths.

A state vector $|\varphi\rangle=\sum_{j}\varphi_{j}|j\rangle$ is called maximally coherent with respect to a given orthonormal product basis $\{|j\rangle\}_{j\in\mathbb{Z}_{d}^{n}}$ of $(\mathbb{C}^{d})^{\otimes n}$ if all its amplitudes have the same modulus $|\varphi_{j}|=d^{-n/2}$. We denote the set of all maximally coherent state vectors in $(\mathbb{C}^{d})^{\otimes n}$ by $\mathcal{S}$. Since $\mathcal{S}$ is the orbit of $d^{-n/2}\sum_{j}|j\rangle$ under the diagonal unitary group $\mathcal{D}$, the normalized Haar measure of the latter induces a normalized measure on $\mathcal{S}$. With a slight abuse of notation we will write $\mu$ for both. Note that despite the connection between $\mathcal{D}$ and $\mathcal{S}$, they behave very differently regarding the quantitative effect of parameter changes: whereas changing a single parameter suffices to move a diagonal unitary a constant $\epsilon$ (say $1/2$) away in operator norm, one has to change a large fraction of parameters, i.e. $\Omega(d^{n})$, in order to move a maximally coherent state by $\epsilon=1/2$ in norm. Nevertheless a similar hardness-of-approximation result holds. The following theorem shows that the subset of $\mathcal{S}$ that can be approximated by circuits of sub-exponential size $O(d^{n}/\ln n)$ is double-exponentially small. The same is true for the subset $\mathcal{S}_{\pm}\subset\mathcal{S}$ of $2^{d^{n}}$ maximally coherent states with real amplitudes $\varphi_{j}=\pm d^{-n/2}$.

Finally, we come back to the explicit examples provided in Cor.1. In order to obtain hardness-of-approximation results for them, we form families of those examples and show that these obey the same estimates as general diagonal unitaries and maximally coherent states (derived in Sec.5.1 and Sec.5.2, respectively). We begin with examples of unitaries.

Let us fix $n$ distinct primes $p_{1},\ldots,p_{n}$ (e.g. the first $n$ primes) and consider the following set of unitaries on $(\mathbb{C}^{d})^{\otimes n}$:

From Cor.1 we know that each of them satisfies $\mathcal{C}_{0}(U_{t})\geq d^{n-4}$. The following theorem shows that the vast majority of the $U_{t}$’s are also hard to approximate in the sense that for every $\epsilon\in[0,1)$ all but a double-exponentially small fraction of the $U_{t}$’s satisfy $\mathcal{C}_{\epsilon}(U_{t},\mathcal{G})=\Omega(d^{n}/\ln n)$. The reason for this is, loosely speaking, that the $U_{t}$’s are uniformly distributed within the set of all diagonal unitaries. As a consequence, the same hardness-of-approximation result (i.e., Thm.4) applies to asymptotically large sets of them. To phrase it more mathematically, the sequence of atomic probability measures $\mu_{N}(U_{t}):=1/N$ supported on $U_{1},\ldots,U_{N}$ converges weakly to the Haar measure of the group of all diagonal unitaries in the limit $N\rightarrow\infty$.