Suppose $A$ is an $n$-qubit unitary such that $A\ket{0}=\sin(\theta)\ket{\psi_1}+\cos(\theta)\ket{\psi_0}$, where $\langle\psi_1|\psi_0\rangle=0$. Let $Q=A(2\ket{0}\!\bra{0}-I)A^\dagger(2\ket{\psi_0}\!\bra{\psi_0}-I)$. Then for every $k\geq 0$,
$$
Q^kA\ket{0}
=
\sin((2k+1)\theta)\ket{\psi_1}+\cos((2k+1)\theta)\ket{\psi_0}.
$$
Given a state-preparation oracle $U$ such that $U\ket{0}=\ket{\psi}=\sqrt{p}\ket{\psi_1}+\sqrt{1-p}\ket{\psi_0}$ with $\langle\psi_1|\psi_0\rangle=0$, and a reflection oracle $R_1=I-2\ket{\psi_1}\!\bra{\psi_1}$. When $p(1-p)=\Omega(1)$, there exists a quantum algorithm that estimates $p$ up to precision $\epsilon$ with failure probability at most $\eta$, using $\mathcal{O}(\log(1/\epsilon)+\log(1/\eta))$ ancilla qubits, $\mathcal{O}(1/(\epsilon\eta))$ queries to $U$, $U^\dagger$, and controlled-$R_1$, and $\mathcal{O}\!\left(n/(\epsilon\eta)+(\log(1/\epsilon)+\log(1/\eta))^2\right)$ elementary gates.
For a parametrized quantum circuit whose dynamical Lie algebra is the orthogonal direct sum $\mathfrak{g} = \bigoplus_j \mathfrak{g}_j$ of its ideals, the loss variance is the reductive Ragone sum $$\operatorname{Var}_\theta[\ell] = \sum_j \frac{P_{\mathfrak{g}_j}(\rho) P_{\mathfrak{g}_j}(O)}{\dim\mathfrak{g}_j},$$ where $P_{\mathfrak{g}_j}$ is the $\mathfrak{g}_j$-purity (derived from cross-ideal Casimir orthogonality); the simple-Lie-algebra case is its single-ideal corollary. When $\dim\mathfrak{g}$ grows exponentially in the qubit count, an exponential barren plateau follows (given the Haar second-moment / Schur projection the formalization carries as a named hypothesis).
Let $f:\{0,1\}^n\to\{0,1\}:x\mapsto x\cdot s\bmod 2$ be the mod-2 inner-product function for an unknown $s\in\{0,1\}^n$. Given access to an oracle $O_f$ such that $O_f\ket{x,y}=\ket{x,y\oplus f(x)}$, there exists a quantum circuit that uses one query to $O_f$ and $2n+1$ Hadamard gates to exactly obtain $s$.
Suppose $f:\{0,1\}^n\to\{0,1\}$ satisfies exactly one of the following two conditions: either $f(x)=f(x')$ for all $x,x'\in\{0,1\}^n$, or $|f^{-1}(0)|=|f^{-1}(1)|=2^{n-1}$. Given access to an oracle $O_f$ such that $O_f\ket{x,y}=\ket{x,y\oplus f(x)}$, there exists a quantum circuit that uses one query to $O_f$ and $2n+1$ Hadamard gates to determine which condition holds with certainty.
For an $n$-qubit variational circuit built from single-qubit gates, the dynamical Lie algebra is spanned by the $3n$ single-site Pauli operators $\{X_j,\,Y_j,\,Z_j\}_{j=1}^{n}$ and equals the orthogonal direct sum of $n$ mutually commuting single-qubit copies of $\mathfrak{su}(2)$: $$\mathfrak g \;=\; \bigoplus_{j=1}^{n}\mathfrak{su}(2)_j,\qquad \dim\mathfrak g = 3n.$$
For an $n$-qubit matchgate (free-fermion) circuit, generated by the Majorana quadratics (the $n(2n-1)$ skew-Hermitian Pauli strings quadratic in the Jordan-Wigner Majorana operators), realized for example by the transverse-field Ising chain (on-site transverse fields with nearest-neighbor Ising couplings), the dynamical Lie algebra is the free-fermion special orthogonal algebra $$\mathfrak g=\mathfrak{so}(2n),\qquad \dim\mathfrak g=n(2n-1),$$ which grows only polynomially in the qubit count $n$.
A variational quantum circuit on $n$ qubits is built from Hermitian generators $\{G_l\}_{l=1}^{L}$ as the product $U(\theta) = \prod_{l=1}^{L} e^{-i \theta_l G_l}$. Its dynamical Lie algebra is the smallest real Lie subalgebra of $\mathfrak{u}(2^n)$ that contains the skew-Hermitian generators $\{i G_l\}_{l=1}^{L}$ and is closed under real-linear combinations and the matrix commutator $[A,B] = AB - BA$: $$\mathfrak{g} = \langle \{ i G_l \}_{l=1}^{L} \rangle_{\operatorname{Lie}}.$$ The formalization represents $\mathfrak{g}$ by the complex Lie subalgebra it generates (its complexification inside the general linear algebra), which has the same dimension as the real algebra.
For the $n$-qubit circuit generated by the skew-symmetric Pauli strings ($P^{\top}=-P$), the dynamical Lie algebra is the special orthogonal algebra $$\mathfrak g \;=\; \mathfrak{so}(2^n),\qquad \dim\mathfrak g=\frac{4^n-2^n}{2}.$$
Let $N\ge 2$ and $a$ be coprime to $N$. Then $U_a = \sum_{x=0}^{N - 1} \ket{ax\bmod N}\!\bra{x}$ is an $N$-dimensional unitary that, for every $k\in\{0,\ldots,r-1\}$, satisfies $$U_a \ket{\psi_k}=e^{2\pi i k/r}\ket{\psi_k}.$$ Here $r$ is the least positive integer such that $a^r\equiv 1\pmod N$ and $\ket{\psi_k} = \sum_{j=0}^{r-1}e^{-2\pi i k j/r}\ket{a^j\bmod N} / \sqrt{r}$. Moreover, $\ket{1}=\sum_{k=0}^{r-1}\ket{\psi_k} / \sqrt{r}$.
Suppose $G=\langle g\rangle$ is a finite cyclic group of known order $N$, and an element $x\in G$ satisfies $x=g^r$ for a unique $r\in\{0,\ldots,N-1\}$. Let $n = \lceil\log_2 N\rceil$. Given access to an oracle $U_x$ such that $U_x\ket{a,b,y}=\ket{a,b,y\,g^a x^{-b}}$, there exists a quantum algorithm that outputs $r$ with success probability at least $2/3$, using one query to $U_x$, $3n$ qubits, $2n$ Hadamard gates, $n(n-1)$ controlled-phase gates, $2\lfloor n/2\rfloor$ SWAP gates, maximal circuit depth $1+2n+n(n-1)+2\lfloor n/2\rfloor$, and $7$ classical arithmetic operations.
For a variational circuit $U=\prod_k e^{i A_k}$ whose skew-Hermitian generators $i A_k$ lie in the dynamical Lie algebra $\mathfrak g$, the Heisenberg-evolved image of any Hermitian observable $O\in i\mathfrak g$ remains in the algebra: $$\mathcal H(O)=U^{\dagger}OU\in i\mathfrak g.$$ Equivalently, the adjoint action of every gate preserves $\mathfrak g$, $e^{-S}\,\mathfrak g\,e^{S}=\mathfrak g$ for $S\in\mathfrak g$, so the $\dim\mathfrak g$-dimensional algebra is closed under Heisenberg evolution.
With respect to a Hilbert–Schmidt-orthonormal Hermitian basis $\{B_j\}_{j=1}^{\dim\mathfrak g}$ of $i\mathfrak g$, write the coordinate vector $c(X)=\big(\langle B_j,X\rangle_{\mathrm{HS}}\big)_{j=1}^{\dim\mathfrak g}$. For a circuit $U=\prod_{k=1}^{L}e^{i A_k}$ with generators in $\mathfrak g$, the coordinates of the Heisenberg-evolved observable follow from those of $O$ by an ordered product of per-gate $\dim\mathfrak g\times\dim\mathfrak g$ transfer matrices, $$c\big(\mathcal H(O)\big)=G_L\cdots G_1\,c(O),\qquad (G_k)_{ij}=\big\langle B_i,\,e^{-i A_k}B_j\,e^{i A_k}\big\rangle_{\mathrm{HS}}=\big(e^{-i\,\operatorname{ad}_{A_k}}\big)_{ij},$$ where $\operatorname{ad}_{A_k}(X)=[A_k,X]$. Each $G_k$ is the adjoint action of one gate written in the basis, so the entire g-sim update runs in the $\dim\mathfrak g$-dimensional coordinate space.
Given a Hermitian observable $O$, a Hermitian generator $G$ with eigenvalues $\{\omega_j\}_{j\in[d]}$, the single-parameter gate $U(x) = e^{ixG}$, and a pure state $|\psi\rangle$, consider the loss $\ell(x) = \langle\psi| U^\dagger(x) O U(x) |\psi\rangle$. Let $\{\Omega_p\}_{p\in[R]} := \{\omega_k - \omega_j : j,k\in[d], \omega_k > \omega_j\}$ be the $R$ unique positive eigenvalue differences of $G$. Assuming these frequencies are equidistant integers $\Omega_p = p$ (without loss of generality, by rescaling), the first and second derivatives of $\ell$ at the origin are given by the generalized parameter-shift rule $$\ell'(0) = \sum_{\mu=1}^{2R} \ell\left(\frac{2\mu-1}{2R}\pi\right) \frac{(-1)^{\mu-1}}{4R \sin^2\left(\frac{2\mu-1}{4R}\pi\right)},$$ $$\ell''(0) = -\ell(0)\frac{2R^2+1}{6} + \sum_{\mu=1}^{2R-1} \ell\left(\frac{\mu\pi}{R}\right) \frac{(-1)^{\mu-1}}{2\sin^2\left(\frac{\mu\pi}{2R}\right)}.$$ For $R=1$ and $R=2$ these reduce to the standard two-term and four-term parameter-shift rules.
Suppose $N=2^n$ and $x$ is a nonzero $N$-bit string. Denote $t=|\{j:x_j=1\}|$. Given access to an $n$-qubit oracle $U_x$ such that $U_x\ket{j}=(-1)^{x_j}\ket{j}$, there exists a quantum algorithm that returns an index $j$ satisfying $x_j=1$ with probability $\sin^2((2k+1)\arcsin\sqrt{t/N})$, using $k$ queries to $U_x$ and $\mathcal{O}(kn)$ elementary gates.
Let $U$ be a unitary. Then for any state $\ket{\psi}$, the output state $\ket{\psi'} = \mathtt{H}_1(\ket{0}\!\bra{0}\otimes I+\ket{1}\!\bra{1}\otimes U)\mathtt{H}_1\ket{0,\psi}$ satisfies
$$
\bra{\psi'}(\ket{0}\!\bra{0}\otimes I)\ket{\psi'}
=
(1+\mathfrak{Re}\{\bra{\psi}U\ket{\psi}\})/2.
$$
Let $\mathfrak g=\langle\{i A_l\}\rangle_{\operatorname{Lie}}\subseteq\mathfrak u(2^n)$ be the dynamical Lie algebra generated by the skew-Hermitian generators $i A_l$ of a variational circuit (with $A_l$ Hermitian), and let $\{B_j\}_{j=1}^{\dim\mathfrak g}$ be a Hilbert–Schmidt-orthonormal basis of the Hermitian sector $i\mathfrak g$, so that $\{i B_j\}$ is a basis of $\mathfrak g$ and the quantum data $\operatorname{Tr}[\rho B_j]$ are real. For every circuit $U=\prod_k e^{i A_k}$ with Hermitian generators $A_k\in i\mathfrak g$ and every Hermitian observable $O\in i\mathfrak g$, the loss reconstructs exactly as $$\operatorname{Tr}\!\big[\,U\rho\,U^{\dagger}O\,\big]=\sum_{j=1}^{\dim\mathfrak g}\big\langle B_j,\,\mathcal H(O)\big\rangle_{\mathrm{HS}}\;\operatorname{Tr}[\rho B_j],$$ where $\mathcal H(O)=U^{\dagger}OU$ is the Heisenberg-evolved observable and $\langle B_j,\mathcal H(O)\rangle_{\mathrm{HS}}=\operatorname{Tr}[B_j\,\mathcal H(O)]$ are its basis coordinates.
Suppose $\{U_k\}_{k=0}^{2^m-1}$ is a set of $n$-qubit unitaries and $A=\sum_{k=0}^{2^m-1}c_kU_k$ for positive coefficients $c_k$. Let $U=\sum_{k=0}^{2^m-1}\ket{k}\!\bra{k}\otimes U_k$, and let $V$ be an $m$-qubit unitary such that $V\ket{0}=\|c\|_1^{-1/2}\sum_{k=0}^{2^m-1}\sqrt{c_k}\ket{k}$. Then $W=(V^\dagger\otimes I^{\otimes n})U(V\otimes I^{\otimes n})$ satisfies
$$
(\bra{0^{m}}\otimes I^{\otimes n})W(\ket{0^{m}}\otimes I^{\otimes n})
=
\|c\|_1^{-1}A.
$$
For the $n$-qubit family built from single-qubit gates, whose dynamical Lie algebra is the product $\mathfrak g=\bigoplus_{j=1}^{n}\mathfrak{su}(2)_j$, fix the input state $\rho=|0\rangle\!\langle0|^{\otimes n}$ and the local observable $O=X_1$ (Pauli $X$ on the first qubit), with loss $\ell_\theta=\operatorname{Tr}[U_\theta\,\rho\,U_\theta^{\dagger}O]$. The loss variance is the closed-form constant $$\operatorname{Var}_\theta[\ell]=\frac{P_{\mathfrak g_1}(\rho)\,P_{\mathfrak g_1}(O)}{\dim\mathfrak{su}(2)_1}=\frac{2^{-n}\cdot 2^{n}}{3}=\frac13,$$ independent of the qubit count $n$, where $\mathfrak g_1=\mathfrak{su}(2)_1$ is the single-qubit ideal of the observable and $P_{\mathfrak g_1}$ its purity. A constant variance does not decay as $C\,b^{-n}$ with $b>1$, so the family has no barren plateau.
Suppose a P-256 ECC instance has known base point $P$ of prime order $r$ and known public key point $Q=[m]P$ for unknown private scalar $m$. There exists a quantum algorithm that returns $m$ with probability at least $2/3$, using $2.33\times 10^3$ logical qubits, $1.26\times 10^{11}$ Toffoli gates, $1.16\times 10^{11}$ maximal Toffoli-gate depth, and $7$ classical arithmetic operations.
Suppose an RSA-2048 public key has known public modulus $N$, whose private prime factors are unknown distinct primes $p$ and $q$. There exists a quantum algorithm that returns $d\in\{p,q\}$ with probability at least $2/3$, using $6.19\times 10^3$ logical qubits, $8.1\times 10^9$ Toffoli gates, $6.42\times 10^9$ maximal circuit depth, and $3.69\times 10^4$ classical arithmetic operations.
For the matchgate family whose dynamical Lie algebra is $\mathfrak{so}(2n)$ (with $n\ge 3$), the single-ideal loss variance $$\operatorname{Var}_\theta[\ell]=\frac{P_{\mathfrak g}(\rho)\,P_{\mathfrak g}(O)}{\dim\mathfrak g},\qquad \dim\mathfrak g=n(2n-1),$$ carries an algebra dimension that grows only polynomially in $n$. When the purity product $P_{\mathfrak g}(\rho)\,P_{\mathfrak g}(O)$ stays bounded below by an inverse polynomial in $n$, the variance is likewise inverse-polynomially bounded below and does not decay as $C\,b^{-n}$ with $b>1$, so the family has no barren plateau. The transverse-field Ising chain realizes this concretely: for the highest-weight state $\rho=|0\rangle\!\langle0|^{\otimes n}$ and a two-body Ising observable $O$ the purities are $P_{\mathfrak g}(\rho)=n/2^n$ and $P_{\mathfrak g}(O)=2^n$, giving the exact inverse-linear variance $\operatorname{Var}=1/(2n-1)$.
Suppose $N\ge 2$, $x$ is an integer with $\gcd(x,N)=1$, and $r$ is the least positive integer satisfying $x^r\equiv 1\pmod N$. Choose $t$ such that $N^2\le 2^t<2N^2$. Given access to a modular-exponentiation oracle $U_x$ such that $U_x\ket{a,y}=\ket{a,y\oplus x^a\bmod N}$, there exists a quantum algorithm that outputs $r$ with success probability at least $\varphi(r)/(3r)$, using one query to $U_x$, $t$ Hadamard gates, $t(t-1)/2$ controlled-phase gates, $\lfloor t/2\rfloor$ SWAP gates, and $\mathcal{O}(\operatorname{poly}(t))$ classical operations.
Suppose $N\ge 2$, $x$ is an integer with $\gcd(x,N)=1$, $r$ is the least positive integer satisfying $x^r\equiv 1\pmod N$, and $q=2^t$ is a multiple of $r$. Given access to an oracle $U_x$ such that $U_x\ket{a,y}=\ket{a,y\oplus x^a\bmod N}$, there exists a quantum algorithm that outputs an index $j=s(q/r)$ for some $s\in\{0,\ldots,r-1\}$, using one query to $U_x$ and $\mathcal{O}(t^2)$ elementary gates.
For the circuit family whose dynamical Lie algebra is $\mathfrak{so}(2^n)$, the single-ideal loss variance $$\operatorname{Var}_\theta[\ell]=\frac{P_{\mathfrak g}(\rho)\,P_{\mathfrak g}(O)}{\dim\mathfrak g},\qquad \dim\mathfrak g=\frac{4^n-2^n}{2},$$ carries an algebra dimension that grows exponentially in the qubit count $n$. With the purities $P_{\mathfrak g}(\rho),\,P_{\mathfrak g}(O)$ bounded, the variance decays as $C\,b^{-n}$ with $b>1$, so the family exhibits a barren plateau.
The effective quantum dimension (capacity) of a QNN is the achievable QFIM rank $D_1(M):=R(M)=\sup_\theta\operatorname{rank}F(\theta)$, with saturated value $R:=\sup_M R(M)$. When the network is overparametrized at parameter count $M$ (achievable rank saturated for every training state), the capacity attains this maximum, $D_1(M)=R$.
The linear loss of a QNN $U_\theta$ with observable $O$ and signed data operator $A=\sum_\mu c_\mu\,\rho_\mu$ (a signed combination of data states $\rho_\mu$) is the single expectation $$\ell(\theta)=\operatorname{Tr}\!\big[\,O\,U_\theta\,A\,U_\theta^{\dagger}\,\big],$$ linear in both $O$ and $A$. With $d$ the Hilbert-space dimension and $r=\min\{\operatorname{rank}A,\operatorname{rank}O\}$, assume (as named hypotheses, per Larocca) that at a minimizer $\theta_*$ the loss Hessian obeys both $\operatorname{rank}\nabla^2\ell(\theta_*)\le\dim\mathfrak g$ and $\operatorname{rank}\nabla^2\ell(\theta_*)\le 2dr-r^2-r$. Then $$\operatorname{rank}\nabla^2\ell(\theta_*)\le\min\{\dim\mathfrak g,\;2dr-r^2-r\}.$$
For a QNN with $M$ parameters and dynamical Lie algebra $\mathfrak g$, let $F(\theta)\in\mathbb R^{M\times M}$ be the quantum Fisher information matrix and $R(M):=\sup_\theta\operatorname{rank}F(\theta)$ the achievable QFIM rank. Then $R(M)$ is bounded by the algebra dimension and non-decreasing in $M$: $$R(M)\le\dim\mathfrak g,\qquad M\le M'\ \Rightarrow\ R(M)\le R(M').$$ Overparametrization therefore persists: once the achievable rank saturates at $M$, it stays saturated for every $M'\ge M$.
Let $O_f$ be a unitary such that $O_f\ket{x,y}=\ket{x,y\oplus f(x)}$ for some Boolean function $f:\{0,1\}^n\to\{0,1\}$. Then for $\ket{-}=(\ket{0}-\ket{1})/\sqrt{2}$,
$$
O_f(\ket{x}\ket{-})
=
(-1)^{f(x)}\ket{x}\ket{-}.
$$
Let $U$ be a unitary with eigenstate $\ket{\psi}$ such that $U\ket{\psi}=e^{i\phi}\ket{\psi}$. Let $\mathtt{CU}$ denote the controlled version of $U$. Then for any coefficients $a,b\in\mathbb{C}$,
$$
\mathtt{CU}\bigl((a\ket{0}+b\ket{1})\ket{\psi}\bigr)
=
(a\ket{0}+e^{i\phi}b\ket{1})\ket{\psi}.
$$
Let $P = \sum_{j=0}^{L} c_j x^j$ be a degree-$L$ real polynomial with parity $L \bmod 2$ such that $|P(x)| \leq 1$ for all $x \in [-1,1]$. Suppose $U$ is a $(1, m, 0)$-block-encoding of an $n$-qubit Hermitian matrix $A$. There exists a quantum circuit $\mathcal{V}$ that implements a $(1, m+1, 0)$-block-encoding of $P(A)$, where $P(A)=\sum_{j=0}^{L} c_j A^j$. The circuit uses one ancilla qubit, $L$ queries to $U$ and $U^\dagger$, and $\mathcal{O}((m+1)L)$ single- and two-qubit gates.
Let $P = \sum_{j=0}^{L} c_j x^j$ be a degree-$L$ complex polynomial such that $|P(x)| \leq 1$ for all $x \in [-1,1]$. Suppose $U$ is a $(1, m, 0)$-block-encoding of an $n$-qubit Hermitian matrix $A$. There exists a quantum circuit $\mathcal{V}$ that implements a $(4, m', 0)$-block-encoding of $P(A)$ for $m \leq m' \leq m + 3$, where $P(A)=\sum_{j=0}^{L} c_j A^j$. The circuit uses at most 3 ancilla qubits, $\mathcal{O}(L)$ queries to $U$ and $U^\dagger$, $\mathcal{O}(1)$ queries to controlled-$U$, and $\mathcal{O}((m+1)L)$ single- and two-qubit gates.
Let $F(x)=\sum_{\ell=-L}^{L}c_\ell e^{i\ell x}$ be a trigonometric polynomial satisfying $|F(x)|\leq 1$ for all $x\in\mathbb{R}$. For any $n$-qubit unitary $U$, there exists a quantum circuit with unitary matrix $\mathcal{V}(U)$ such that
$$
(\bra{0}\otimes I^{\otimes n})\mathcal{V}(U)(\ket{0}\otimes I^{\otimes n})
= F(U).
$$
Here $F(U)=\sum_{\ell=-L}^{L}c_\ell U^\ell$. The circuit uses one ancilla qubit, $2L$ queries to controlled-$U$ or controlled-$U^\dagger$, and $4L+3$ one-qubit rotations.
Let $P(x)=\sum_{j=0}^{L} c_j x^j$ be a degree-$L$ real polynomial with parity $L \bmod 2$ such that $|P(x)|\leq 1$ for all $x\in[-1,1]$. Suppose $U$ is a unitary and $\Pi,\widetilde{\Pi}$ are orthogonal projectors, and let $A=\widetilde{\Pi}U\Pi$. There exists a quantum circuit implementing a unitary $V$ such that $$P^{(\mathrm{SV})}(A)=(\bra{+}\otimes\Pi_L)V(\ket{+}\otimes\Pi),$$ where $\Pi_L=\widetilde{\Pi}$ when $L$ is odd and $\Pi_L=\Pi$ when $L$ is even. The circuit uses one ancilla qubit, $L$ total queries to $U$ or $U^\dagger$, $L$ queries to $\mathtt{C}_{\Pi}\mathtt{NOT}$, $L$ queries to $\mathtt{C}_{\widetilde{\Pi}}\mathtt{NOT}$, and $L$ controlled phase gates.
Suppose $p$ and $q$ are unknown distinct prime numbers satisfying $2^{n-1}<p,q<2^n$, and let $N=pq$ be known. There exists a quantum algorithm that returns $d\in\{p,q\}$ with probability at least $1-\eta$, using at most $6n+0.004n\log(2n)$ logical qubits, $\mathcal{O}(\log(1/\eta))\bigl(2.4n^3+0.004n^3\log(2n)\bigr)$ Toffoli gates, $\mathcal{O}(\log(1/\eta))\bigl(2000n^2+4n^2\log(2n)\bigr)$ maximal circuit depth, and $\mathcal{O}(\operatorname{poly}(n,\log(1/\eta)))$ classical arithmetic operations.
Suppose $p$ and $q$ are unknown distinct prime numbers. Let $N=pq$ be known and let $n=\lceil\log_2 N\rceil$. There exists a quantum algorithm that returns $d \in \{p, q\}$ with probability at least $1-\eta$, using $3n+\mathcal{O}(\log n)$ logical qubits, $\mathcal{O}(\log(1/\eta))\bigl(0.4n^3+0.0006n^3\log n\bigr)$ Toffoli gates, $\mathcal{O}(\log(1/\eta))\bigl(600n^2+n^2\log n\bigr)$ maximal circuit depth, and $\mathcal{O}(\operatorname{poly}(n,\log(1/\eta)))$ classical arithmetic operations.
A variational quantum neural network with $M$ trainable parameters $\theta$ has, over its optimization landscape, achievable QFIM rank $R(M) = \sup_\theta \operatorname{rank} F(\theta)$, with saturated value $R = \sup_M R(M)$. The network is overparametrized at parameter count $M$ when the achievable rank saturates, $R(M) = R$; the critical parameter count $M_c = \inf\{\,M : R(M) = R\,\}$ is the least such $M$, beyond which adding parameters explores no new state-space directions of the optimization landscape.
Fix a unit reference state $\psi$ ($\langle\psi|\psi\rangle=1$) and write $\langle X\rangle:=\langle\psi|X|\psi\rangle$. For bare, $\theta$-independent Hermitian generators $H_1,\dots,H_M$ ($H_j=H_j^{\dagger}$), define the centred states $|c_j\rangle:=(H_j-\langle H_j\rangle)|\psi\rangle$. The quantum Fisher information matrix $F\in\mathbb R^{M\times M}$ is $$[F]_{jk}=4\operatorname{Re}\!\big(\langle H_jH_k\rangle-\langle H_j\rangle\langle H_k\rangle\big)=4\operatorname{Re}\langle c_j|c_k\rangle.$$ As four times the real part of the Gram matrix $\langle c_j|c_k\rangle$, it is symmetric positive semidefinite, $F=F^{\top}\succeq 0$. If the generators lie in the real span of a Hermitian basis of the dynamical Lie algebra $\mathfrak g$, then $\operatorname{rank}F\le\dim\mathfrak g$, and in every case $\operatorname{rank}F\le M$. The generators are the bare reference-frame $H_j$, not the Heisenberg-rotated $U_j^{\dagger}H_jU_j$; identifying $F$ with the Fubini--Study metric is a named bridge hypothesis, not proved here.
Let $n\geq 1$ and $N=2^n$. There is an $n$-qubit quantum circuit using $n$ Hadamard gates, $n(n-1)/2$ controlled-phase gates, and $\lfloor n/2\rfloor$ SWAP gates whose unitary matrix is $\mathtt{QFT}_{N}$ satisfying
$$
\mathtt{QFT}_{N}\ket{j}
=
\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\omega_N^{jk}\ket{k}.
$$
A quantum kernel encodes a classical input $x$ through a data-encoding circuit $U(x)$ into the feature state $|\phi(x)\rangle = U(x)|0\rangle$ on $n$ qubits. The fidelity quantum kernel is the squared overlap of feature states, $$K(x,x') = |\langle \phi(x) | \phi(x')\rangle|^2 = |\langle 0| U^\dagger(x') U(x) |0\rangle|^2.$$ For any finite data set $\{x_i\}$ the Gram matrix $K_{ij}=K(x_i,x_j)$ is positive semidefinite, so $K$ is a valid kernel.
Given access to the controlled version of an $n$-qubit unitary $U$ and its eigenstate $\ket{\psi}$ such that $U\ket{\psi}=e^{2\pi i\theta}\ket{\psi}$, there is a quantum algorithm that estimates $\theta$ up to precision $2^{-n_a}$ and failure probability at most $1-4/\pi^2$, using $n_a$ ancilla qubits, $\mathcal{O}(2^{n_a})$ queries to controlled-$U$, and $\mathcal{O}(n_a^2)$ single-qubit gates and CNOT gates.
Suppose Alice has an $n$-qubit state $\ket{\psi}$ and Alice and Bob share $n$ Bell states. There exists a quantum protocol using $2n$ classical bits to transfer $\ket{\psi}$ to Bob locally.
There exists a sequence of phase factors $\Phi=(\phi_0,\ldots,\phi_d)\in\mathbb{R}^{d+1}$ such that
$$
U_\Phi(x)
=
e^{i\phi_0 Z}\prod_{j=1}^{d}\large( \begin{bmatrix}
x & \sqrt{1-x^2}\\
\sqrt{1-x^2} & -x
\end{bmatrix}e^{i\phi_j Z} \large)
=
\begin{bmatrix}
P(x) & -Q(x)\sqrt{1-x^2}\\
Q^*(x)\sqrt{1-x^2} & P^*(x)
\end{bmatrix}
$$
if and only if $P,Q\in\mathbb{C}[x]$ satisfy $\deg(P)\leq d$, $\deg(Q)\leq d-1$, $P$ has parity $d\bmod 2$, $Q$ has parity $(d-1)\bmod 2$, and $|P(x)|^2+(1-x^2)|Q(x)|^2=1$ for all $x\in[-1,1]$.
Suppose $s\in\{0,1\}^n$ is nonzero, and $f:\{0,1\}^n\to\{0,1\}^n$ satisfies $f(x)=f(y)$ if and only if $x=y$ or $y=x\oplus s$. Given access to an oracle $O_f$ such that $O_f\ket{x,y}=\ket{x,y\oplus f(x)}$, there exists a quantum algorithm that determines $s$ using expected $\mathcal{O}(n)$ queries to $O_f$, $\mathcal{O}(n^2)$ Hadamard gates, and $\mathcal{O}(n^3)$ classical operations over $\mathbb{F}_2$.
For a parametrized quantum circuit whose dynamical Lie algebra $\mathfrak{g}$ is simple, $\mathfrak{g} \simeq \mathfrak{su}(d)$ (dimension $d^2-1$, centerless), the loss variance reduces to a single term $$\operatorname{Var}_\theta[\ell] = \frac{P_{\mathfrak{g}}(\rho)\, P_{\mathfrak{g}}(O)}{d^2-1}.$$ In particular, for $d = 2^n$ the dimension $\dim\mathfrak{g} = 4^n-1$ grows exponentially in the qubit count $n$, so the loss exhibits an exponential barren plateau (under the Haar second-moment / Schur hypothesis carried as a named input).
Suppose Alice has a $2n$-bit classical string $x$ and Alice and Bob share $n$ Bell states. There exists a quantum protocol using $n$ qubits for Bob to recover $x$ locally.
For any $n$-qubit states $\ket{\psi}$ and $\ket{\phi}$, the state $\ket{\psi'} = \mathtt{H}_1 \mathtt{CSWAP}\mathtt{H}_1\ket{0,\psi,\phi}$ satisfies
$$
\bra{\psi'}(\ket{1}\!\bra{1}\otimes I^{\otimes 2n})\ket{\psi'}
=
(1-|\langle\psi|\phi\rangle|^2) / 2.
$$
There exist angles $\omega\in\mathbb{R}$ and $\boldsymbol{\theta},\boldsymbol{\phi}\in\mathbb{R}^{L+1}$ such that
$$
U_{\omega,\boldsymbol{\theta},\boldsymbol{\phi}}^{L}(x)
=
R_Z(\omega)\,R_Y(\theta_0)R_Z(\phi_0)
\prod_{j=1}^{L}\bigl(R_Z(x)\,R_Y(\theta_j)R_Z(\phi_j)\bigr)
=
\begin{bmatrix}
P(x) & -Q(x)\\
Q^*(x) & P^*(x)
\end{bmatrix}
$$
if and only if $P,Q\in\mathbb{C}[e^{ix/2},e^{-ix/2}]$ satisfy $\deg(P)\leq L$, $\deg(Q)\leq L$, $P$ and $Q$ have parity $L\bmod 2$, and $|P(x)|^2+|Q(x)|^2=1$ for all $x\in\mathbb{R}$.
No matching algorithms.
Search · Algorithms
Amplitude amplification
Suppose $A$ is an $n$-qubit unitary such that $A\ket{0}=\sin(\theta)\ket{\psi_1}+\cos(\theta)\ket{\psi_0}$, where $\langle\psi_1|\psi_0\rangle=0$. Let $Q=A(2\ket{0}\!\bra{0}-I)A^\dagger(2\ket{\psi_0}\!\bra{\psi_0}-I)$. Then for every $k\geq 0$,
$$
Q^kA\ket{0}
=
\sin((2k+1)\theta)\ket{\psi_1}+\cos((2k+1)\theta)\ket{\psi_0}.
$$
Given a state-preparation oracle $U$ such that $U\ket{0}=\ket{\psi}=\sqrt{p}\ket{\psi_1}+\sqrt{1-p}\ket{\psi_0}$ with $\langle\psi_1|\psi_0\rangle=0$, and a reflection oracle $R_1=I-2\ket{\psi_1}\!\bra{\psi_1}$. When $p(1-p)=\Omega(1)$, there exists a quantum algorithm that estimates $p$ up to precision $\epsilon$ with failure probability at most $\eta$, using $\mathcal{O}(\log(1/\epsilon)+\log(1/\eta))$ ancilla qubits, $\mathcal{O}(1/(\epsilon\eta))$ queries to $U$, $U^\dagger$, and controlled-$R_1$, and $\mathcal{O}\!\left(n/(\epsilon\eta)+(\log(1/\epsilon)+\log(1/\eta))^2\right)$ elementary gates.
For a parametrized quantum circuit whose dynamical Lie algebra is the orthogonal direct sum $\mathfrak{g} = \bigoplus_j \mathfrak{g}_j$ of its ideals, the loss variance is the reductive Ragone sum $$\operatorname{Var}_\theta[\ell] = \sum_j \frac{P_{\mathfrak{g}_j}(\rho) P_{\mathfrak{g}_j}(O)}{\dim\mathfrak{g}_j},$$ where $P_{\mathfrak{g}_j}$ is the $\mathfrak{g}_j$-purity (derived from cross-ideal Casimir orthogonality); the simple-Lie-algebra case is its single-ideal corollary. When $\dim\mathfrak{g}$ grows exponentially in the qubit count, an exponential barren plateau follows (given the Haar second-moment / Schur projection the formalization carries as a named hypothesis).
Let $f:\{0,1\}^n\to\{0,1\}:x\mapsto x\cdot s\bmod 2$ be the mod-2 inner-product function for an unknown $s\in\{0,1\}^n$. Given access to an oracle $O_f$ such that $O_f\ket{x,y}=\ket{x,y\oplus f(x)}$, there exists a quantum circuit that uses one query to $O_f$ and $2n+1$ Hadamard gates to exactly obtain $s$.
Suppose $f:\{0,1\}^n\to\{0,1\}$ satisfies exactly one of the following two conditions: either $f(x)=f(x')$ for all $x,x'\in\{0,1\}^n$, or $|f^{-1}(0)|=|f^{-1}(1)|=2^{n-1}$. Given access to an oracle $O_f$ such that $O_f\ket{x,y}=\ket{x,y\oplus f(x)}$, there exists a quantum circuit that uses one query to $O_f$ and $2n+1$ Hadamard gates to determine which condition holds with certainty.
Dynamical Lie algebra of a local single-qubit-gate circuit
For an $n$-qubit variational circuit built from single-qubit gates, the dynamical Lie algebra is spanned by the $3n$ single-site Pauli operators $\{X_j,\,Y_j,\,Z_j\}_{j=1}^{n}$ and equals the orthogonal direct sum of $n$ mutually commuting single-qubit copies of $\mathfrak{su}(2)$: $$\mathfrak g \;=\; \bigoplus_{j=1}^{n}\mathfrak{su}(2)_j,\qquad \dim\mathfrak g = 3n.$$
M. Cerezo, Martin Larocca, Diego Garcia-Martin, N. L. Diaz, Paolo Braccia, Enrico Fontana, Manuel S. Rudolph, Pablo Bermejo, Aroosa Ijaz, Supanut Thanasilp, Eric R. Anschuetz, Zoe Holmes, 2023
Dynamical Lie algebra of a matchgate (free-fermion) circuit
For an $n$-qubit matchgate (free-fermion) circuit, generated by the Majorana quadratics (the $n(2n-1)$ skew-Hermitian Pauli strings quadratic in the Jordan-Wigner Majorana operators), realized for example by the transverse-field Ising chain (on-site transverse fields with nearest-neighbor Ising couplings), the dynamical Lie algebra is the free-fermion special orthogonal algebra $$\mathfrak g=\mathfrak{so}(2n),\qquad \dim\mathfrak g=n(2n-1),$$ which grows only polynomially in the qubit count $n$.
A variational quantum circuit on $n$ qubits is built from Hermitian generators $\{G_l\}_{l=1}^{L}$ as the product $U(\theta) = \prod_{l=1}^{L} e^{-i \theta_l G_l}$. Its dynamical Lie algebra is the smallest real Lie subalgebra of $\mathfrak{u}(2^n)$ that contains the skew-Hermitian generators $\{i G_l\}_{l=1}^{L}$ and is closed under real-linear combinations and the matrix commutator $[A,B] = AB - BA$: $$\mathfrak{g} = \langle \{ i G_l \}_{l=1}^{L} \rangle_{\operatorname{Lie}}.$$ The formalization represents $\mathfrak{g}$ by the complex Lie subalgebra it generates (its complexification inside the general linear algebra), which has the same dimension as the real algebra.
Dynamical Lie algebra of an orthogonally-generated circuit
For the $n$-qubit circuit generated by the skew-symmetric Pauli strings ($P^{\top}=-P$), the dynamical Lie algebra is the special orthogonal algebra $$\mathfrak g \;=\; \mathfrak{so}(2^n),\qquad \dim\mathfrak g=\frac{4^n-2^n}{2}.$$
Let $N\ge 2$ and $a$ be coprime to $N$. Then $U_a = \sum_{x=0}^{N - 1} \ket{ax\bmod N}\!\bra{x}$ is an $N$-dimensional unitary that, for every $k\in\{0,\ldots,r-1\}$, satisfies $$U_a \ket{\psi_k}=e^{2\pi i k/r}\ket{\psi_k}.$$ Here $r$ is the least positive integer such that $a^r\equiv 1\pmod N$ and $\ket{\psi_k} = \sum_{j=0}^{r-1}e^{-2\pi i k j/r}\ket{a^j\bmod N} / \sqrt{r}$. Moreover, $\ket{1}=\sum_{k=0}^{r-1}\ket{\psi_k} / \sqrt{r}$.
Suppose $G=\langle g\rangle$ is a finite cyclic group of known order $N$, and an element $x\in G$ satisfies $x=g^r$ for a unique $r\in\{0,\ldots,N-1\}$. Let $n = \lceil\log_2 N\rceil$. Given access to an oracle $U_x$ such that $U_x\ket{a,b,y}=\ket{a,b,y\,g^a x^{-b}}$, there exists a quantum algorithm that outputs $r$ with success probability at least $2/3$, using one query to $U_x$, $3n$ qubits, $2n$ Hadamard gates, $n(n-1)$ controlled-phase gates, $2\lfloor n/2\rfloor$ SWAP gates, maximal circuit depth $1+2n+n(n-1)+2\lfloor n/2\rfloor$, and $7$ classical arithmetic operations.
$$G$$
Finite cyclic group.
$$g$$
Generator of the finite cyclic group.
$$N$$
Known group order.
$$n$$
Register width, defined as the ceiling of log_2 N.
$$x$$
Group element whose discrete logarithm is recovered.
g-sim: the evolved observable stays in the algebra
For a variational circuit $U=\prod_k e^{i A_k}$ whose skew-Hermitian generators $i A_k$ lie in the dynamical Lie algebra $\mathfrak g$, the Heisenberg-evolved image of any Hermitian observable $O\in i\mathfrak g$ remains in the algebra: $$\mathcal H(O)=U^{\dagger}OU\in i\mathfrak g.$$ Equivalently, the adjoint action of every gate preserves $\mathfrak g$, $e^{-S}\,\mathfrak g\,e^{S}=\mathfrak g$ for $S\in\mathfrak g$, so the $\dim\mathfrak g$-dimensional algebra is closed under Heisenberg evolution.
M. Cerezo, Martin Larocca, Diego Garcia-Martin, N. L. Diaz, Paolo Braccia, Enrico Fontana, Manuel S. Rudolph, Pablo Bermejo, Aroosa Ijaz, Supanut Thanasilp, Eric R. Anschuetz, Zoe Holmes, 2023
With respect to a Hilbert–Schmidt-orthonormal Hermitian basis $\{B_j\}_{j=1}^{\dim\mathfrak g}$ of $i\mathfrak g$, write the coordinate vector $c(X)=\big(\langle B_j,X\rangle_{\mathrm{HS}}\big)_{j=1}^{\dim\mathfrak g}$. For a circuit $U=\prod_{k=1}^{L}e^{i A_k}$ with generators in $\mathfrak g$, the coordinates of the Heisenberg-evolved observable follow from those of $O$ by an ordered product of per-gate $\dim\mathfrak g\times\dim\mathfrak g$ transfer matrices, $$c\big(\mathcal H(O)\big)=G_L\cdots G_1\,c(O),\qquad (G_k)_{ij}=\big\langle B_i,\,e^{-i A_k}B_j\,e^{i A_k}\big\rangle_{\mathrm{HS}}=\big(e^{-i\,\operatorname{ad}_{A_k}}\big)_{ij},$$ where $\operatorname{ad}_{A_k}(X)=[A_k,X]$. Each $G_k$ is the adjoint action of one gate written in the basis, so the entire g-sim update runs in the $\dim\mathfrak g$-dimensional coordinate space.
M. Cerezo, Martin Larocca, Diego Garcia-Martin, N. L. Diaz, Paolo Braccia, Enrico Fontana, Manuel S. Rudolph, Pablo Bermejo, Aroosa Ijaz, Supanut Thanasilp, Eric R. Anschuetz, Zoe Holmes, 2023
Given a Hermitian observable $O$, a Hermitian generator $G$ with eigenvalues $\{\omega_j\}_{j\in[d]}$, the single-parameter gate $U(x) = e^{ixG}$, and a pure state $|\psi\rangle$, consider the loss $\ell(x) = \langle\psi| U^\dagger(x) O U(x) |\psi\rangle$. Let $\{\Omega_p\}_{p\in[R]} := \{\omega_k - \omega_j : j,k\in[d], \omega_k > \omega_j\}$ be the $R$ unique positive eigenvalue differences of $G$. Assuming these frequencies are equidistant integers $\Omega_p = p$ (without loss of generality, by rescaling), the first and second derivatives of $\ell$ at the origin are given by the generalized parameter-shift rule $$\ell'(0) = \sum_{\mu=1}^{2R} \ell\left(\frac{2\mu-1}{2R}\pi\right) \frac{(-1)^{\mu-1}}{4R \sin^2\left(\frac{2\mu-1}{4R}\pi\right)},$$ $$\ell''(0) = -\ell(0)\frac{2R^2+1}{6} + \sum_{\mu=1}^{2R-1} \ell\left(\frac{\mu\pi}{R}\right) \frac{(-1)^{\mu-1}}{2\sin^2\left(\frac{\mu\pi}{2R}\right)}.$$ For $R=1$ and $R=2$ these reduce to the standard two-term and four-term parameter-shift rules.
Suppose $N=2^n$ and $x$ is a nonzero $N$-bit string. Denote $t=|\{j:x_j=1\}|$. Given access to an $n$-qubit oracle $U_x$ such that $U_x\ket{j}=(-1)^{x_j}\ket{j}$, there exists a quantum algorithm that returns an index $j$ satisfying $x_j=1$ with probability $\sin^2((2k+1)\arcsin\sqrt{t/N})$, using $k$ queries to $U_x$ and $\mathcal{O}(kn)$ elementary gates.
Let $U$ be a unitary. Then for any state $\ket{\psi}$, the output state $\ket{\psi'} = \mathtt{H}_1(\ket{0}\!\bra{0}\otimes I+\ket{1}\!\bra{1}\otimes U)\mathtt{H}_1\ket{0,\psi}$ satisfies
$$
\bra{\psi'}(\ket{0}\!\bra{0}\otimes I)\ket{\psi'}
=
(1+\mathfrak{Re}\{\bra{\psi}U\ket{\psi}\})/2.
$$
Let $\mathfrak g=\langle\{i A_l\}\rangle_{\operatorname{Lie}}\subseteq\mathfrak u(2^n)$ be the dynamical Lie algebra generated by the skew-Hermitian generators $i A_l$ of a variational circuit (with $A_l$ Hermitian), and let $\{B_j\}_{j=1}^{\dim\mathfrak g}$ be a Hilbert–Schmidt-orthonormal basis of the Hermitian sector $i\mathfrak g$, so that $\{i B_j\}$ is a basis of $\mathfrak g$ and the quantum data $\operatorname{Tr}[\rho B_j]$ are real. For every circuit $U=\prod_k e^{i A_k}$ with Hermitian generators $A_k\in i\mathfrak g$ and every Hermitian observable $O\in i\mathfrak g$, the loss reconstructs exactly as $$\operatorname{Tr}\!\big[\,U\rho\,U^{\dagger}O\,\big]=\sum_{j=1}^{\dim\mathfrak g}\big\langle B_j,\,\mathcal H(O)\big\rangle_{\mathrm{HS}}\;\operatorname{Tr}[\rho B_j],$$ where $\mathcal H(O)=U^{\dagger}OU$ is the Heisenberg-evolved observable and $\langle B_j,\mathcal H(O)\rangle_{\mathrm{HS}}=\operatorname{Tr}[B_j\,\mathcal H(O)]$ are its basis coordinates.
M. Cerezo, Martin Larocca, Diego Garcia-Martin, N. L. Diaz, Paolo Braccia, Enrico Fontana, Manuel S. Rudolph, Pablo Bermejo, Aroosa Ijaz, Supanut Thanasilp, Eric R. Anschuetz, Zoe Holmes, 2023
Suppose $\{U_k\}_{k=0}^{2^m-1}$ is a set of $n$-qubit unitaries and $A=\sum_{k=0}^{2^m-1}c_kU_k$ for positive coefficients $c_k$. Let $U=\sum_{k=0}^{2^m-1}\ket{k}\!\bra{k}\otimes U_k$, and let $V$ be an $m$-qubit unitary such that $V\ket{0}=\|c\|_1^{-1/2}\sum_{k=0}^{2^m-1}\sqrt{c_k}\ket{k}$. Then $W=(V^\dagger\otimes I^{\otimes n})U(V\otimes I^{\otimes n})$ satisfies
$$
(\bra{0^{m}}\otimes I^{\otimes n})W(\ket{0^{m}}\otimes I^{\otimes n})
=
\|c\|_1^{-1}A.
$$
For the $n$-qubit family built from single-qubit gates, whose dynamical Lie algebra is the product $\mathfrak g=\bigoplus_{j=1}^{n}\mathfrak{su}(2)_j$, fix the input state $\rho=|0\rangle\!\langle0|^{\otimes n}$ and the local observable $O=X_1$ (Pauli $X$ on the first qubit), with loss $\ell_\theta=\operatorname{Tr}[U_\theta\,\rho\,U_\theta^{\dagger}O]$. The loss variance is the closed-form constant $$\operatorname{Var}_\theta[\ell]=\frac{P_{\mathfrak g_1}(\rho)\,P_{\mathfrak g_1}(O)}{\dim\mathfrak{su}(2)_1}=\frac{2^{-n}\cdot 2^{n}}{3}=\frac13,$$ independent of the qubit count $n$, where $\mathfrak g_1=\mathfrak{su}(2)_1$ is the single-qubit ideal of the observable and $P_{\mathfrak g_1}$ its purity. A constant variance does not decay as $C\,b^{-n}$ with $b>1$, so the family has no barren plateau.
Suppose a P-256 ECC instance has known base point $P$ of prime order $r$ and known public key point $Q=[m]P$ for unknown private scalar $m$. There exists a quantum algorithm that returns $m$ with probability at least $2/3$, using $2.33\times 10^3$ logical qubits, $1.26\times 10^{11}$ Toffoli gates, $1.16\times 10^{11}$ maximal Toffoli-gate depth, and $7$ classical arithmetic operations.
Suppose an RSA-2048 public key has known public modulus $N$, whose private prime factors are unknown distinct primes $p$ and $q$. There exists a quantum algorithm that returns $d\in\{p,q\}$ with probability at least $2/3$, using $6.19\times 10^3$ logical qubits, $8.1\times 10^9$ Toffoli gates, $6.42\times 10^9$ maximal circuit depth, and $3.69\times 10^4$ classical arithmetic operations.
For the matchgate family whose dynamical Lie algebra is $\mathfrak{so}(2n)$ (with $n\ge 3$), the single-ideal loss variance $$\operatorname{Var}_\theta[\ell]=\frac{P_{\mathfrak g}(\rho)\,P_{\mathfrak g}(O)}{\dim\mathfrak g},\qquad \dim\mathfrak g=n(2n-1),$$ carries an algebra dimension that grows only polynomially in $n$. When the purity product $P_{\mathfrak g}(\rho)\,P_{\mathfrak g}(O)$ stays bounded below by an inverse polynomial in $n$, the variance is likewise inverse-polynomially bounded below and does not decay as $C\,b^{-n}$ with $b>1$, so the family has no barren plateau. The transverse-field Ising chain realizes this concretely: for the highest-weight state $\rho=|0\rangle\!\langle0|^{\otimes n}$ and a two-body Ising observable $O$ the purities are $P_{\mathfrak g}(\rho)=n/2^n$ and $P_{\mathfrak g}(O)=2^n$, giving the exact inverse-linear variance $\operatorname{Var}=1/(2n-1)$.
M. Cerezo, Martin Larocca, Diego Garcia-Martin, N. L. Diaz, Paolo Braccia, Enrico Fontana, Manuel S. Rudolph, Pablo Bermejo, Aroosa Ijaz, Supanut Thanasilp, Eric R. Anschuetz, Zoe Holmes, 2023
Suppose $N\ge 2$, $x$ is an integer with $\gcd(x,N)=1$, and $r$ is the least positive integer satisfying $x^r\equiv 1\pmod N$. Choose $t$ such that $N^2\le 2^t<2N^2$. Given access to a modular-exponentiation oracle $U_x$ such that $U_x\ket{a,y}=\ket{a,y\oplus x^a\bmod N}$, there exists a quantum algorithm that outputs $r$ with success probability at least $\varphi(r)/(3r)$, using one query to $U_x$, $t$ Hadamard gates, $t(t-1)/2$ controlled-phase gates, $\lfloor t/2\rfloor$ SWAP gates, and $\mathcal{O}(\operatorname{poly}(t))$ classical operations.
$$N$$
Integer modulus.
$$x$$
Integer base coprime to N.
$$r$$
Multiplicative order of x modulo N.
$$t$$
Phase-register bit length.
$$U_x$$
Modular-exponentiation oracle.
$$a$$
Exponent-register basis value.
$$y$$
Work-register basis value.
$$\varphi$$
Euler totient function.
$$\mathcal{O}$$
Asymptotic upper-bound notation in the unverified public target.
Suppose $N\ge 2$, $x$ is an integer with $\gcd(x,N)=1$, $r$ is the least positive integer satisfying $x^r\equiv 1\pmod N$, and $q=2^t$ is a multiple of $r$. Given access to an oracle $U_x$ such that $U_x\ket{a,y}=\ket{a,y\oplus x^a\bmod N}$, there exists a quantum algorithm that outputs an index $j=s(q/r)$ for some $s\in\{0,\ldots,r-1\}$, using one query to $U_x$ and $\mathcal{O}(t^2)$ elementary gates.
For the circuit family whose dynamical Lie algebra is $\mathfrak{so}(2^n)$, the single-ideal loss variance $$\operatorname{Var}_\theta[\ell]=\frac{P_{\mathfrak g}(\rho)\,P_{\mathfrak g}(O)}{\dim\mathfrak g},\qquad \dim\mathfrak g=\frac{4^n-2^n}{2},$$ carries an algebra dimension that grows exponentially in the qubit count $n$. With the purities $P_{\mathfrak g}(\rho),\,P_{\mathfrak g}(O)$ bounded, the variance decays as $C\,b^{-n}$ with $b>1$, so the family exhibits a barren plateau.
The effective quantum dimension (capacity) of a QNN is the achievable QFIM rank $D_1(M):=R(M)=\sup_\theta\operatorname{rank}F(\theta)$, with saturated value $R:=\sup_M R(M)$. When the network is overparametrized at parameter count $M$ (achievable rank saturated for every training state), the capacity attains this maximum, $D_1(M)=R$.
The linear loss of a QNN $U_\theta$ with observable $O$ and signed data operator $A=\sum_\mu c_\mu\,\rho_\mu$ (a signed combination of data states $\rho_\mu$) is the single expectation $$\ell(\theta)=\operatorname{Tr}\!\big[\,O\,U_\theta\,A\,U_\theta^{\dagger}\,\big],$$ linear in both $O$ and $A$. With $d$ the Hilbert-space dimension and $r=\min\{\operatorname{rank}A,\operatorname{rank}O\}$, assume (as named hypotheses, per Larocca) that at a minimizer $\theta_*$ the loss Hessian obeys both $\operatorname{rank}\nabla^2\ell(\theta_*)\le\dim\mathfrak g$ and $\operatorname{rank}\nabla^2\ell(\theta_*)\le 2dr-r^2-r$. Then $$\operatorname{rank}\nabla^2\ell(\theta_*)\le\min\{\dim\mathfrak g,\;2dr-r^2-r\}.$$
For a QNN with $M$ parameters and dynamical Lie algebra $\mathfrak g$, let $F(\theta)\in\mathbb R^{M\times M}$ be the quantum Fisher information matrix and $R(M):=\sup_\theta\operatorname{rank}F(\theta)$ the achievable QFIM rank. Then $R(M)$ is bounded by the algebra dimension and non-decreasing in $M$: $$R(M)\le\dim\mathfrak g,\qquad M\le M'\ \Rightarrow\ R(M)\le R(M').$$ Overparametrization therefore persists: once the achievable rank saturates at $M$, it stays saturated for every $M'\ge M$.
Let $O_f$ be a unitary such that $O_f\ket{x,y}=\ket{x,y\oplus f(x)}$ for some Boolean function $f:\{0,1\}^n\to\{0,1\}$. Then for $\ket{-}=(\ket{0}-\ket{1})/\sqrt{2}$,
$$
O_f(\ket{x}\ket{-})
=
(-1)^{f(x)}\ket{x}\ket{-}.
$$
Let $U$ be a unitary with eigenstate $\ket{\psi}$ such that $U\ket{\psi}=e^{i\phi}\ket{\psi}$. Let $\mathtt{CU}$ denote the controlled version of $U$. Then for any coefficients $a,b\in\mathbb{C}$,
$$
\mathtt{CU}\bigl((a\ket{0}+b\ket{1})\ket{\psi}\bigr)
=
(a\ket{0}+e^{i\phi}b\ket{1})\ket{\psi}.
$$
Polynomial transformation on block encodings (Hermitian, real with parity)
Let $P = \sum_{j=0}^{L} c_j x^j$ be a degree-$L$ real polynomial with parity $L \bmod 2$ such that $|P(x)| \leq 1$ for all $x \in [-1,1]$. Suppose $U$ is a $(1, m, 0)$-block-encoding of an $n$-qubit Hermitian matrix $A$. There exists a quantum circuit $\mathcal{V}$ that implements a $(1, m+1, 0)$-block-encoding of $P(A)$, where $P(A)=\sum_{j=0}^{L} c_j A^j$. The circuit uses one ancilla qubit, $L$ queries to $U$ and $U^\dagger$, and $\mathcal{O}((m+1)L)$ single- and two-qubit gates.
$P$
Polynomial applied to the encoded Hermitian matrix.
Polynomial transformation on block encodings (Hermitian)
Let $P = \sum_{j=0}^{L} c_j x^j$ be a degree-$L$ complex polynomial such that $|P(x)| \leq 1$ for all $x \in [-1,1]$. Suppose $U$ is a $(1, m, 0)$-block-encoding of an $n$-qubit Hermitian matrix $A$. There exists a quantum circuit $\mathcal{V}$ that implements a $(4, m', 0)$-block-encoding of $P(A)$ for $m \leq m' \leq m + 3$, where $P(A)=\sum_{j=0}^{L} c_j A^j$. The circuit uses at most 3 ancilla qubits, $\mathcal{O}(L)$ queries to $U$ and $U^\dagger$, $\mathcal{O}(1)$ queries to controlled-$U$, and $\mathcal{O}((m+1)L)$ single- and two-qubit gates.
$P$
Polynomial applied to the encoded Hermitian matrix.
Let $F(x)=\sum_{\ell=-L}^{L}c_\ell e^{i\ell x}$ be a trigonometric polynomial satisfying $|F(x)|\leq 1$ for all $x\in\mathbb{R}$. For any $n$-qubit unitary $U$, there exists a quantum circuit with unitary matrix $\mathcal{V}(U)$ such that
$$
(\bra{0}\otimes I^{\otimes n})\mathcal{V}(U)(\ket{0}\otimes I^{\otimes n})
= F(U).
$$
Here $F(U)=\sum_{\ell=-L}^{L}c_\ell U^\ell$. The circuit uses one ancilla qubit, $2L$ queries to controlled-$U$ or controlled-$U^\dagger$, and $4L+3$ one-qubit rotations.
Let $P(x)=\sum_{j=0}^{L} c_j x^j$ be a degree-$L$ real polynomial with parity $L \bmod 2$ such that $|P(x)|\leq 1$ for all $x\in[-1,1]$. Suppose $U$ is a unitary and $\Pi,\widetilde{\Pi}$ are orthogonal projectors, and let $A=\widetilde{\Pi}U\Pi$. There exists a quantum circuit implementing a unitary $V$ such that $$P^{(\mathrm{SV})}(A)=(\bra{+}\otimes\Pi_L)V(\ket{+}\otimes\Pi),$$ where $\Pi_L=\widetilde{\Pi}$ when $L$ is odd and $\Pi_L=\Pi$ when $L$ is even. The circuit uses one ancilla qubit, $L$ total queries to $U$ or $U^\dagger$, $L$ queries to $\mathtt{C}_{\Pi}\mathtt{NOT}$, $L$ queries to $\mathtt{C}_{\widetilde{\Pi}}\mathtt{NOT}$, and $L$ controlled phase gates.
$P$
Real polynomial applied through singular-value transformation.
Suppose $p$ and $q$ are unknown distinct prime numbers satisfying $2^{n-1}<p,q<2^n$, and let $N=pq$ be known. There exists a quantum algorithm that returns $d\in\{p,q\}$ with probability at least $1-\eta$, using at most $6n+0.004n\log(2n)$ logical qubits, $\mathcal{O}(\log(1/\eta))\bigl(2.4n^3+0.004n^3\log(2n)\bigr)$ Toffoli gates, $\mathcal{O}(\log(1/\eta))\bigl(2000n^2+4n^2\log(2n)\bigr)$ maximal circuit depth, and $\mathcal{O}(\operatorname{poly}(n,\log(1/\eta)))$ classical arithmetic operations.
$$p$$
Unknown prime factor.
$$q$$
Unknown prime factor.
$$n$$
Factor bit length.
$$N$$
Known RSA modulus.
$$d$$
Recovered prime factor.
$$\eta$$
Failure probability parameter.
$$\mathcal{O}$$
Asymptotic upper-bound notation in the unverified public target.
Suppose $p$ and $q$ are unknown distinct prime numbers. Let $N=pq$ be known and let $n=\lceil\log_2 N\rceil$. There exists a quantum algorithm that returns $d \in \{p, q\}$ with probability at least $1-\eta$, using $3n+\mathcal{O}(\log n)$ logical qubits, $\mathcal{O}(\log(1/\eta))\bigl(0.4n^3+0.0006n^3\log n\bigr)$ Toffoli gates, $\mathcal{O}(\log(1/\eta))\bigl(600n^2+n^2\log n\bigr)$ maximal circuit depth, and $\mathcal{O}(\operatorname{poly}(n,\log(1/\eta)))$ classical arithmetic operations.
$$p$$
Unknown prime factor.
$$q$$
Unknown prime factor.
$$N$$
Known semiprime modulus.
$$n$$
Bit length of N.
$$d$$
Recovered prime factor.
$$\eta$$
Failure probability parameter.
$$\mathcal{O}$$
Asymptotic upper-bound notation in the unverified public target.
A variational quantum neural network with $M$ trainable parameters $\theta$ has, over its optimization landscape, achievable QFIM rank $R(M) = \sup_\theta \operatorname{rank} F(\theta)$, with saturated value $R = \sup_M R(M)$. The network is overparametrized at parameter count $M$ when the achievable rank saturates, $R(M) = R$; the critical parameter count $M_c = \inf\{\,M : R(M) = R\,\}$ is the least such $M$, beyond which adding parameters explores no new state-space directions of the optimization landscape.
Fix a unit reference state $\psi$ ($\langle\psi|\psi\rangle=1$) and write $\langle X\rangle:=\langle\psi|X|\psi\rangle$. For bare, $\theta$-independent Hermitian generators $H_1,\dots,H_M$ ($H_j=H_j^{\dagger}$), define the centred states $|c_j\rangle:=(H_j-\langle H_j\rangle)|\psi\rangle$. The quantum Fisher information matrix $F\in\mathbb R^{M\times M}$ is $$[F]_{jk}=4\operatorname{Re}\!\big(\langle H_jH_k\rangle-\langle H_j\rangle\langle H_k\rangle\big)=4\operatorname{Re}\langle c_j|c_k\rangle.$$ As four times the real part of the Gram matrix $\langle c_j|c_k\rangle$, it is symmetric positive semidefinite, $F=F^{\top}\succeq 0$. If the generators lie in the real span of a Hermitian basis of the dynamical Lie algebra $\mathfrak g$, then $\operatorname{rank}F\le\dim\mathfrak g$, and in every case $\operatorname{rank}F\le M$. The generators are the bare reference-frame $H_j$, not the Heisenberg-rotated $U_j^{\dagger}H_jU_j$; identifying $F$ with the Fubini--Study metric is a named bridge hypothesis, not proved here.
Let $n\geq 1$ and $N=2^n$. There is an $n$-qubit quantum circuit using $n$ Hadamard gates, $n(n-1)/2$ controlled-phase gates, and $\lfloor n/2\rfloor$ SWAP gates whose unitary matrix is $\mathtt{QFT}_{N}$ satisfying
$$
\mathtt{QFT}_{N}\ket{j}
=
\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\omega_N^{jk}\ket{k}.
$$
$\mathtt{QFT}_{N}$
Quantum Fourier transform over N computational-basis states.
$\omega_N$
Primitive N-th root of unity used in the Fourier phase.
A quantum kernel encodes a classical input $x$ through a data-encoding circuit $U(x)$ into the feature state $|\phi(x)\rangle = U(x)|0\rangle$ on $n$ qubits. The fidelity quantum kernel is the squared overlap of feature states, $$K(x,x') = |\langle \phi(x) | \phi(x')\rangle|^2 = |\langle 0| U^\dagger(x') U(x) |0\rangle|^2.$$ For any finite data set $\{x_i\}$ the Gram matrix $K_{ij}=K(x_i,x_j)$ is positive semidefinite, so $K$ is a valid kernel.
Given access to the controlled version of an $n$-qubit unitary $U$ and its eigenstate $\ket{\psi}$ such that $U\ket{\psi}=e^{2\pi i\theta}\ket{\psi}$, there is a quantum algorithm that estimates $\theta$ up to precision $2^{-n_a}$ and failure probability at most $1-4/\pi^2$, using $n_a$ ancilla qubits, $\mathcal{O}(2^{n_a})$ queries to controlled-$U$, and $\mathcal{O}(n_a^2)$ single-qubit gates and CNOT gates.
Suppose Alice has an $n$-qubit state $\ket{\psi}$ and Alice and Bob share $n$ Bell states. There exists a quantum protocol using $2n$ classical bits to transfer $\ket{\psi}$ to Bob locally.
There exists a sequence of phase factors $\Phi=(\phi_0,\ldots,\phi_d)\in\mathbb{R}^{d+1}$ such that
$$
U_\Phi(x)
=
e^{i\phi_0 Z}\prod_{j=1}^{d}\large( \begin{bmatrix}
x & \sqrt{1-x^2}\\
\sqrt{1-x^2} & -x
\end{bmatrix}e^{i\phi_j Z} \large)
=
\begin{bmatrix}
P(x) & -Q(x)\sqrt{1-x^2}\\
Q^*(x)\sqrt{1-x^2} & P^*(x)
\end{bmatrix}
$$
if and only if $P,Q\in\mathbb{C}[x]$ satisfy $\deg(P)\leq d$, $\deg(Q)\leq d-1$, $P$ has parity $d\bmod 2$, $Q$ has parity $(d-1)\bmod 2$, and $|P(x)|^2+(1-x^2)|Q(x)|^2=1$ for all $x\in[-1,1]$.
Suppose $s\in\{0,1\}^n$ is nonzero, and $f:\{0,1\}^n\to\{0,1\}^n$ satisfies $f(x)=f(y)$ if and only if $x=y$ or $y=x\oplus s$. Given access to an oracle $O_f$ such that $O_f\ket{x,y}=\ket{x,y\oplus f(x)}$, there exists a quantum algorithm that determines $s$ using expected $\mathcal{O}(n)$ queries to $O_f$, $\mathcal{O}(n^2)$ Hadamard gates, and $\mathcal{O}(n^3)$ classical operations over $\mathbb{F}_2$.
For a parametrized quantum circuit whose dynamical Lie algebra $\mathfrak{g}$ is simple, $\mathfrak{g} \simeq \mathfrak{su}(d)$ (dimension $d^2-1$, centerless), the loss variance reduces to a single term $$\operatorname{Var}_\theta[\ell] = \frac{P_{\mathfrak{g}}(\rho)\, P_{\mathfrak{g}}(O)}{d^2-1}.$$ In particular, for $d = 2^n$ the dimension $\dim\mathfrak{g} = 4^n-1$ grows exponentially in the qubit count $n$, so the loss exhibits an exponential barren plateau (under the Haar second-moment / Schur hypothesis carried as a named input).
Suppose Alice has a $2n$-bit classical string $x$ and Alice and Bob share $n$ Bell states. There exists a quantum protocol using $n$ qubits for Bob to recover $x$ locally.
For any $n$-qubit states $\ket{\psi}$ and $\ket{\phi}$, the state $\ket{\psi'} = \mathtt{H}_1 \mathtt{CSWAP}\mathtt{H}_1\ket{0,\psi,\phi}$ satisfies
$$
\bra{\psi'}(\ket{1}\!\bra{1}\otimes I^{\otimes 2n})\ket{\psi'}
=
(1-|\langle\psi|\phi\rangle|^2) / 2.
$$
$\mathtt{H}_1$
Hadamard gate acting on the control qubit.
$\mathtt{CSWAP}$
Controlled-SWAP gate exchanging the two target registers when the control qubit is one.
There exist angles $\omega\in\mathbb{R}$ and $\boldsymbol{\theta},\boldsymbol{\phi}\in\mathbb{R}^{L+1}$ such that
$$
U_{\omega,\boldsymbol{\theta},\boldsymbol{\phi}}^{L}(x)
=
R_Z(\omega)\,R_Y(\theta_0)R_Z(\phi_0)
\prod_{j=1}^{L}\bigl(R_Z(x)\,R_Y(\theta_j)R_Z(\phi_j)\bigr)
=
\begin{bmatrix}
P(x) & -Q(x)\\
Q^*(x) & P^*(x)
\end{bmatrix}
$$
if and only if $P,Q\in\mathbb{C}[e^{ix/2},e^{-ix/2}]$ satisfy $\deg(P)\leq L$, $\deg(Q)\leq L$, $P$ and $Q$ have parity $L\bmod 2$, and $|P(x)|^2+|Q(x)|^2=1$ for all $x\in\mathbb{R}$.