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}.
$$
Let $0<\epsilon\leq1$, $0<\eta\leq1$,
$n_a=\lceil\log_2(\pi/(\epsilon\eta))\rceil$,
$k=2^{n_a}-1$ and $0<p<1$ such that $p(1-p)=\Omega(1)$.
Consider an $n$-qubit state-preparation oracle $U$ such that
$U\ket{0}=\sqrt{p}\ket{\psi_1}+\sqrt{1-p}\ket{\psi_0}$,
and a reflection oracle $R_1=I-2\ket{\psi_1}\!\bra{\psi_1}$
for some orthogonal states $\ket{\psi_0}$ and $\ket{\psi_1}$.
Given access to $U$, $U^\dagger$ and controlled-$R_1$,
there exists a quantum algorithm that estimates $p$
to precision $\epsilon$ with failure probability at most $\eta$,
using at most $n+n_a$ logical qubits,
$k+1$ queries to $U$, $k$ queries to $U^\dagger$,
$k$ queries to controlled-$R_1$, and the following gate counts:
$$
\begin{array}{c|ccc}
n & \text{Toffoli gates} & \text{CNOT gates}
& \text{Single-qubit gates} \\ \hline
1 & 0
& n_a(n_a-1)+3\lfloor n_a/2\rfloor+k
& n_a(3n_a+1)/2+2k \\
2 & k
& n_a(n_a-1)+3\lfloor n_a/2\rfloor
& n_a(3n_a+1)/2+7k \\
3 & 4k
& n_a(n_a-1)+3\lfloor n_a/2\rfloor
& n_a(3n_a+1)/2+9k \\
4 & 10k
& n_a(n_a-1)+3\lfloor n_a/2\rfloor
& n_a(3n_a+1)/2+11k \\
n\geq5 & 8(n-3)k
& n_a(n_a-1)+3\lfloor n_a/2\rfloor
& n_a(3n_a+1)/2+(2n+3)k
\end{array}
$$
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 1 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 1 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}$.
Let $p>3$ be prime, $f=\lceil\log_2p\rceil$,
$h=\lceil\log_2(2f)\rceil$,
$E/\mathbb{F}_p:y^2=x^3+a x+b$ be an elliptic curve, and
$Q\in E(\mathbb{F}_p)$ be a fixed classical point other than
the identity $\mathcal{O}$. There exists a reversible quantum circuit
on $37f+27+3h$ qubits, using at most $35f+26+3h$ ancilla qubits
and $(22656h+247488)f^2+(23120h-41836)f+3550$ Toffoli gates,
whose action on computational basis states satisfies
$$
\mathtt{ECADD}_{Q}\ket{c}\ket{P}
=\ket{c}\ket{P+cQ}
$$
for every control bit $c\in\{0,1\}$ and every point
$P\in E(\mathbb{F}_p)$ distinct from $\mathcal{O}$, $Q$, and $-Q$.
Suppose $G=\langle g\rangle$ is a finite cyclic group of known
order $N$, and an element $x\in G$ is known.
Let $n=\lceil\log_2N\rceil$, $t=\lceil\log_2(12N)\rceil$,
and $k=\lceil\log(1/3)/
\log(1-N\varphi(N)/2^{2t+2})\rceil$.
Given access to an oracle $U_x$ satisfying
$U_x\ket{a,b,y}=\ket{a,b,y\,g^a x^{-b}}$,
there exists a quantum algorithm that returns
$r\in\{0,\ldots,N-1\}$ satisfying $x=g^r$ with probability
at least $2/3$, using at most
$2t+n$ logical qubits, $k$ queries to $U_x$,
$k(2t^2+4t+6\lfloor t/2\rfloor)$ CNOT gates,
$k(3t^2+23t+n)$ single-qubit gates,
$3+k(\frac{5t(t-1)}{2}+57t+2n+109)$
quantum computation time, and $2kt$ group operations.
Let $d\geq0$ be an integer, $t\geq0$ be real,
and $H_1,H_2\in\mathbb{C}^{d\times d}$
be Hermitian matrices.
Then
$$
\left\|
e^{-it(H_1+H_2)}-e^{-itH_1}e^{-itH_2}
\right\|
\leq
\frac{t^2}{2}\left\|H_1H_2-H_2H_1\right\|,
$$
where
$\|M\|=\sup\{\|Mv\|_2:v\in\mathbb{C}^d,\ \|v\|_2\leq1\}$.
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)=\left(\langle B_j,X\rangle_{\mathrm{HS}}\right)_{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\left(\mathcal H(O)\right)=G_L\cdots G_1\,c(O),\qquad (G_k)_{ij}=\left\langle B_i,\,e^{-i A_k}B_j\,e^{i A_k}\right\rangle_{\mathrm{HS}}=\left(e^{-i\,\operatorname{ad}_{A_k}}\right)_{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$,
where $R\geq1$.
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
$$
\begin{aligned}
\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)}.
\end{aligned}
$$
For $R=1$ and $R=2$ these reduce to the standard two-term
and four-term parameter-shift rules.
Let $n\geq1$ be an integer, $N=2^n$, $x$ be a nonzero
$N$-bit string, and $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}$, for every integer $k\geq0$,
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 at most $n+1$ logical qubits, $k$ queries to $U_x$,
and the following gate counts:
$$
\begin{array}{c|ccc}
n & \text{Toffoli gates} & \text{CNOT gates}
& \text{Single-qubit gates} \\ \hline
1 & 0 & 0 & 1+3k \\
2 & 0 & k & 2+8k \\
3 & k & 0 & 3+15k \\
4 & 4k & 0 & 4+19k \\
5 & 10k & 0 & 5+23k \\
n\geq6 & 8(n-4)k & 0 & n+(4n+3)k
\end{array}
$$
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}\!\left[\,U\rho\,U^{\dagger}O\,\right]=\sum_{j=1}^{\dim\mathfrak g}\left\langle B_j,\,\mathcal H(O)\right\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.
Let $P$ be the standard P-256 base point of prime order $r$,
and $Q\in\langle P\rangle$ be a known point other than
the point at infinity.
There exists a quantum algorithm that returns the unique scalar
$m\in\{0,\ldots,r-1\}$ satisfying $Q=[m]P$ with probability
at least $0.99$, using at most
$818$ logical qubits,
$5.32\times10^{26}$ Toffoli gates,
$1.33\times10^{26}$ CNOT gates,
$3.04\times10^{19}$ single-qubit gates,
$6.65\times10^{26}$ quantum computation time,
$155$ kB of classical memory,
and $7.87\times10^{10}$ classical operations.
Suppose $(p,q)$ is drawn uniformly from the ordered pairs of
distinct primes satisfying $2^{1023}<p,q<2^{1024}$, with
known $N=pq$ satisfying $2^{2047}<N<2^{2048}$.
There exists a quantum algorithm that returns a factor
$d\in\{p,q\}$ with probability at least $0.99$, using at most
$4097$ logical qubits,
$1.18\times10^{17}$ Toffoli gates,
$4.17\times10^{14}$ CNOT gates,
$1.49\times10^8$ single-qubit gates,
$1.18\times10^{17}$ quantum computation time,
$132$ GB of classical memory,
and $1.54\times10^{19}$ classical 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)$.
Let $m,n\geq0$, $1\leq N\leq2^n$, and $0\leq a<N$
be integers with $\gcd(a,N)=1$.
There exists a reversible quantum circuit
on $m+3n$ qubits, using at most $2n$ ancilla qubits,
$24mn\left((3744n+624)\lceil\log_2(n+1)\rceil+160n+65\right)+3n$ Toffoli gates, $24mn^2\left(39\lceil\log_2(n+1)\rceil+2\right)+n$ CNOT gates, and $2$ single-qubit gates,
whose action on computational basis states satisfies
$$
U_{N,a}\ket{z}\ket{y}
=\ket{z}\ket{y\oplus(a^z\bmod N)}
$$
for every $z<2^m$ and $y<2^n$.
Let $N\geq2$ and $x$ be integers with $\gcd(x,N)=1$,
$r$ be the least positive integer satisfying $x^r\equiv1\pmod N$,
$n=\lceil\log_2N\rceil$, and $t=\lceil\log_2(N^2)\rceil$.
Given access to a $(t+n)$-qubit 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 probability at least $\varphi(r)/(3r)$,
using at most $t+n$ logical qubits, 1 query to $U_x$,
$t(t-1)+3\lfloor t/2\rfloor$ CNOT gates,
$t(3t+1)/2$ single-qubit gates,
$12t+11n+17$ classical bits,
and $12t^2+4nt+64t+4n+57$ classical operations.
Let $N\geq2$ and $x\geq0$ be integers with $\gcd(x,N)=1$,
$r$ be the least positive integer satisfying $x^r\equiv1\pmod N$,
$n=\lceil\log_2N\rceil$, and $q=2^t$ be a multiple of $r$
for an integer $t\geq1$.
Given access to a $(t+n)$-qubit 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\}$ with probability one,
using at most $t+n$ logical qubits, 1 query to $U_x$,
$t(t-1)+3\lfloor t/2\rfloor$ CNOT gates,
and $t(3t+1)/2$ single-qubit gates.
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}\!\left[\,O\,U_\theta\,A\,U_\theta^{\dagger}\,\right],$ 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}\left((a\ket{0}+b\ket{1})\ket{\psi}\right)
=
(a\ket{0}+e^{i\phi}b\ket{1})\ket{\psi}.
$$
Let $m,n,L\geq0$ be integers,
$P=\sum_{j=0}^{L}c_jx^j$ be a degree-$L$ real polynomial
with parity $L\bmod2$ such that $|P(x)|\leq1$ for every
$x\in[-1,1]$, and $U$ be a $(1,m,0)$-block-encoding
of an $n$-qubit Hermitian matrix $A$.
Given access to $U$ and $U^\dagger$, there exists
a quantum circuit $\mathcal V$ that implements
a $(1,m+1,0)$-block-encoding of
$P(A)=\sum_{j=0}^{L}c_jA^j$, using at most
1 ancilla qubit, $L$ queries to $U$ and $U^\dagger$,
$192mL$ CNOT gates, and $((296m+3)L+2)$ single-qubit gates.
Let $m,n,L\geq0$ be integers,
$P=\sum_{j=0}^{L}c_jx^j$ be a degree-$L$ complex polynomial
such that $|P(x)|\leq1$ for every $x\in[-1,1]$,
and $U$ be a $(1,m,0)$-block-encoding
of an $n$-qubit Hermitian matrix $A$.
Given access to $U$, $U^\dagger$ and controlled-$U$,
there exists a quantum circuit $\mathcal V$ that implements
a $(4,m',0)$-block-encoding of
$P(A)=\sum_{j=0}^{L}c_jA^j$ for $m\leq m'\leq m+3$,
using at most 3 ancilla qubits,
$L$ queries to $U$ and $U^\dagger$,
1 query to controlled-$U$,
$((192m+6)L+6)$ CNOT gates,
and $((296m+6)L+13)$ single-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.
Let $p>3$ be prime, $E/\mathbb F_p$ be a short Weierstrass
elliptic curve, $P\in E(\mathbb F_p)$ be a known point
of known prime order $r$, $Q\in\langle P\rangle$ be a known
point other than the point at infinity, and $0<\eta\leq1$.
Set $f=\lceil\log_2p\rceil$, $t=\lceil\log_2(12r)\rceil$,
and $k=\lceil\log\eta/
\log(1-r(r-1)/2^{2t+2})\rceil$.
Given access to an oracle $U_{P,Q}$ satisfying
$U_{P,Q}\ket{a,b,R}=\ket{a,b,R+[a]P-[b]Q}$,
there exists a quantum algorithm that returns
$m\in\{0,\ldots,r-1\}$ satisfying $Q=[m]P$
with probability at least $1-\eta$, using at most
$2t+2f+1$ logical qubits,
$k$ queries to $U_{P,Q}$,
$k(2t^2+4t+6\lfloor t/2\rfloor)$ CNOT gates,
$k(3t^2+25t+4f+3)$ single-qubit gates,
$2t+2f+2+k\left(5t^2+248ft+721t+8f+6\lfloor t/2\rfloor+125\right)$
quantum computation time,
$\max\{18t^2+70t+70,18f^2+72f+69\}+6f+4t+8$
classical bits,
and $k(248ft+686t+119)+1$ classical operations.
Let $0<\eta<1$ and
$k=\lceil\log(\eta/2)/\log(147/256)\rceil$.
For all sufficiently large integers $n$, set
$\ell=\lfloor(n+2)/2\rfloor$ and suppose $(p,q)$ is drawn
uniformly from the ordered pairs of distinct primes satisfying
$2^{n-1}<p,q<2^n$, with known $N=pq$ satisfying
$2^{2n-1}<N<2^{2n}$.
Given access to oracles $V_{N,g,x}$ satisfying
$V_{N,g,x}\ket{a,b,y}
=\ket{a,b,y\oplus(g^a x^{-b}\bmod N)}$
for units $g,x$ modulo $N$, there exists a quantum algorithm
that returns a factor $d\in\{p,q\}$ with probability
at least $1-\eta$, using at most
$3n+2\ell+1$ logical qubits,
$16k$ queries to $V_{N,g,x}$,
$16k\left(n^2+2n\ell+2\ell^2+n
+3\lfloor(n+\ell+1)/2\rfloor+3\lfloor\ell/2\rfloor\right)$
CNOT gates,
$k(24n^2+48n\ell+48\ell^2+107n+98\ell+49)-3n-2\ell-1$
single-qubit gates,
$k\left(40(n+\ell)^2+56(n+\ell)+113\right)-1$
quantum computation time,
$880803934n+293601328\ell+587202961$ classical bits,
and $k(2^{52}n+1)$ classical operations.
Suppose $p$ and $q$ are unknown distinct primes and $N=pq$
is known. Let $n=\lceil\log_2N\rceil$, $0<\eta\leq1$,
and $k=\lceil\log\eta/\log(1-1/(48n))\rceil$.
Given access to modular-exponentiation oracles $U_{N,a}$
satisfying $U_{N,a}\ket{z,y}
=\ket{z,y\oplus(a^z\bmod N)}$,
there exists a quantum algorithm that returns a factor
$d\in\{p,q\}$ with probability at least $1-\eta$,
using at most $3n$ logical qubits,
$k$ queries to $U_{N,a}$,
$k(4n^2+n)$ CNOT gates,
$k(6n^2+4n)$ single-qubit gates,
$3n+k(66n^2+232n+317)+2$ quantum computation time,
$k(22n+1)+70n+42$ classical bits,
and $k(56n^2+222n+316)+2$ classical operations.
Let $d,m,N$ be positive integers, $B,t\geq0$,
$H_1,\ldots,H_m\in\mathbb{C}^{d\times d}$ be Hermitian
matrices with $\|H_j\|\leq B$, and $h_1,\ldots,h_m\geq0$
satisfy $\lambda=\sum_{j=1}^{m}h_j>0$.
Set $p_j=h_j/\lambda$ and $T=t\lambda$, and define
$E(X)=\sum_{j=1}^{m}p_j e^{-i(T/N)H_j}X e^{i(T/N)H_j}$
and
$U(X)=e^{-i(T/N)\sum_{j=1}^{m}p_jH_j}
X e^{i(T/N)\sum_{j=1}^{m}p_jH_j}$
for $X\in\mathbb{C}^{d\times d}$.
Then
$$
\|U^N-E^N\|_{1\to1}
\leq
B^2\left(e^{TB}(2+TB)+2\right)\frac{T^2}{N},
$$
where powers denote repeated composition,
$\|M\|=\sup\{\|Mv\|_2:v\in\mathbb{C}^d,\ \|v\|_2\leq1\}$,
$\|X\|_1=\operatorname{Tr}\sqrt{X^\dagger X}$,
and
$\|\Phi\|_{1\to1}=\sup_{\|X\|_1\leq1}\|\Phi(X)\|_1$.
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}\!\left(\langle H_jH_k\rangle-\langle H_j\rangle\langle H_k\rangle\right)=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\geq1$, $N=2^n$ and $\omega=e^{2\pi i/N}$.
There exists an $n$-qubit quantum circuit using at most
$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^{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}$,
for every integer $n_a\geq1$, there exists a quantum algorithm
that estimates $\theta$ modulo $1$ up to precision $2^{-n_a}$
and failure probability at most $1-4/\pi^2$,
using at most $n_a$ ancilla qubits,
$2^{n_a}-1$ queries to controlled-$U$,
$n_a(n_a-1)+3\lfloor n_a/2\rfloor$ CNOT gates,
and $n_a(3n_a+1)/2$ single-qubit 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.
Let $d\geq 0$. There exists a sequence of phase factors
$\Phi=(\phi_0,\ldots,\phi_d)\in\mathbb{R}^{d+1}$ such that,
for every $x\in[-1,1]$,
$$
U_\Phi(x)
=
e^{i\phi_0 Z}\prod_{j=1}^{d}\left(
\begin{bmatrix}
x & -\sqrt{1-x^2}\\
\sqrt{1-x^2} & x
\end{bmatrix}e^{i\phi_j Z}\right)
=
\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]$.
At $d=0$, the degree condition on $Q$ means $Q=0$.
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}\left(R_Z(x)\,R_Y(\theta_j)R_Z(\phi_j)\right)
=
\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}$.
Let $n\geq1$, $N=2^n$, $\omega=e^{2\pi i/N}$,
and $\ket{\psi}=\sum_{j=0}^{N-1}\alpha_j\ket{j}$
be an $n$-qubit state.
There exists an $n$-qubit quantum circuit using at most
$n$ Hadamard gates, $n(n-1)/2$ single-qubit phase gates and $n$ classical bits to
obtain a classical output $k\in\{0,\ldots,N-1\}$ with distribution
$$
\Pr[k]
=
\frac{1}{N}
\left|\sum_{j=0}^{N-1}\alpha_j\omega^{jk}\right|^2.
$$
No matching algorithms.
Search · Primitives
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}.
$$
Let $0<\epsilon\leq1$, $0<\eta\leq1$,
$n_a=\lceil\log_2(\pi/(\epsilon\eta))\rceil$,
$k=2^{n_a}-1$ and $0<p<1$ such that $p(1-p)=\Omega(1)$.
Consider an $n$-qubit state-preparation oracle $U$ such that
$U\ket{0}=\sqrt{p}\ket{\psi_1}+\sqrt{1-p}\ket{\psi_0}$,
and a reflection oracle $R_1=I-2\ket{\psi_1}\!\bra{\psi_1}$
for some orthogonal states $\ket{\psi_0}$ and $\ket{\psi_1}$.
Given access to $U$, $U^\dagger$ and controlled-$R_1$,
there exists a quantum algorithm that estimates $p$
to precision $\epsilon$ with failure probability at most $\eta$,
using at most $n+n_a$ logical qubits,
$k+1$ queries to $U$, $k$ queries to $U^\dagger$,
$k$ queries to controlled-$R_1$, and the following gate counts:
$$
\begin{array}{c|ccc}
n & \text{Toffoli gates} & \text{CNOT gates}
& \text{Single-qubit gates} \\ \hline
1 & 0
& n_a(n_a-1)+3\lfloor n_a/2\rfloor+k
& n_a(3n_a+1)/2+2k \\
2 & k
& n_a(n_a-1)+3\lfloor n_a/2\rfloor
& n_a(3n_a+1)/2+7k \\
3 & 4k
& n_a(n_a-1)+3\lfloor n_a/2\rfloor
& n_a(3n_a+1)/2+9k \\
4 & 10k
& n_a(n_a-1)+3\lfloor n_a/2\rfloor
& n_a(3n_a+1)/2+11k \\
n\geq5 & 8(n-3)k
& n_a(n_a-1)+3\lfloor n_a/2\rfloor
& n_a(3n_a+1)/2+(2n+3)k
\end{array}
$$
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 1 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 1 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}$.
Let $p>3$ be prime, $f=\lceil\log_2p\rceil$,
$h=\lceil\log_2(2f)\rceil$,
$E/\mathbb{F}_p:y^2=x^3+a x+b$ be an elliptic curve, and
$Q\in E(\mathbb{F}_p)$ be a fixed classical point other than
the identity $\mathcal{O}$. There exists a reversible quantum circuit
on $37f+27+3h$ qubits, using at most $35f+26+3h$ ancilla qubits
and $(22656h+247488)f^2+(23120h-41836)f+3550$ Toffoli gates,
whose action on computational basis states satisfies
$$
\mathtt{ECADD}_{Q}\ket{c}\ket{P}
=\ket{c}\ket{P+cQ}
$$
for every control bit $c\in\{0,1\}$ and every point
$P\in E(\mathbb{F}_p)$ distinct from $\mathcal{O}$, $Q$, and $-Q$.
$$p$$
Prime field characteristic.
$$f$$
Canonical binary width of one prime-field coordinate, equal to the ceiling of log base two of p.
$$E$$
Elliptic curve over the prime field.
$$a$$
Linear coefficient in the short Weierstrass curve equation.
$$b$$
Constant coefficient in the short Weierstrass curve equation.
$$P$$
Input elliptic-curve point encoded in the quantum register.
$$Q$$
Fixed classical nonidentity point added conditionally by the circuit.
Suppose $G=\langle g\rangle$ is a finite cyclic group of known
order $N$, and an element $x\in G$ is known.
Let $n=\lceil\log_2N\rceil$, $t=\lceil\log_2(12N)\rceil$,
and $k=\lceil\log(1/3)/
\log(1-N\varphi(N)/2^{2t+2})\rceil$.
Given access to an oracle $U_x$ satisfying
$U_x\ket{a,b,y}=\ket{a,b,y\,g^a x^{-b}}$,
there exists a quantum algorithm that returns
$r\in\{0,\ldots,N-1\}$ satisfying $x=g^r$ with probability
at least $2/3$, using at most
$2t+n$ logical qubits, $k$ queries to $U_x$,
$k(2t^2+4t+6\lfloor t/2\rfloor)$ CNOT gates,
$k(3t^2+23t+n)$ single-qubit gates,
$3+k(\frac{5t(t-1)}{2}+57t+2n+109)$
quantum computation time, and $2kt$ group operations.
$$G$$
Finite cyclic group.
$$g$$
Generator of the finite cyclic group.
$$N$$
Known group order.
$$x$$
Group element whose discrete logarithm is recovered.
Let $d\geq0$ be an integer, $t\geq0$ be real,
and $H_1,H_2\in\mathbb{C}^{d\times d}$
be Hermitian matrices.
Then
$$
\left\|
e^{-it(H_1+H_2)}-e^{-itH_1}e^{-itH_2}
\right\|
\leq
\frac{t^2}{2}\left\|H_1H_2-H_2H_1\right\|,
$$
where
$\|M\|=\sup\{\|Mv\|_2:v\in\mathbb{C}^d,\ \|v\|_2\leq1\}$.
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)=\left(\langle B_j,X\rangle_{\mathrm{HS}}\right)_{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\left(\mathcal H(O)\right)=G_L\cdots G_1\,c(O),\qquad (G_k)_{ij}=\left\langle B_i,\,e^{-i A_k}B_j\,e^{i A_k}\right\rangle_{\mathrm{HS}}=\left(e^{-i\,\operatorname{ad}_{A_k}}\right)_{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$,
where $R\geq1$.
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
$$
\begin{aligned}
\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)}.
\end{aligned}
$$
For $R=1$ and $R=2$ these reduce to the standard two-term
and four-term parameter-shift rules.
Let $n\geq1$ be an integer, $N=2^n$, $x$ be a nonzero
$N$-bit string, and $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}$, for every integer $k\geq0$,
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 at most $n+1$ logical qubits, $k$ queries to $U_x$,
and the following gate counts:
$$
\begin{array}{c|ccc}
n & \text{Toffoli gates} & \text{CNOT gates}
& \text{Single-qubit gates} \\ \hline
1 & 0 & 0 & 1+3k \\
2 & 0 & k & 2+8k \\
3 & k & 0 & 3+15k \\
4 & 4k & 0 & 4+19k \\
5 & 10k & 0 & 5+23k \\
n\geq6 & 8(n-4)k & 0 & n+(4n+3)k
\end{array}
$$
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}\!\left[\,U\rho\,U^{\dagger}O\,\right]=\sum_{j=1}^{\dim\mathfrak g}\left\langle B_j,\,\mathcal H(O)\right\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.
Let $P$ be the standard P-256 base point of prime order $r$,
and $Q\in\langle P\rangle$ be a known point other than
the point at infinity.
There exists a quantum algorithm that returns the unique scalar
$m\in\{0,\ldots,r-1\}$ satisfying $Q=[m]P$ with probability
at least $0.99$, using at most
$818$ logical qubits,
$5.32\times10^{26}$ Toffoli gates,
$1.33\times10^{26}$ CNOT gates,
$3.04\times10^{19}$ single-qubit gates,
$6.65\times10^{26}$ quantum computation time,
$155$ kB of classical memory,
and $7.87\times10^{10}$ classical operations.
Suppose $(p,q)$ is drawn uniformly from the ordered pairs of
distinct primes satisfying $2^{1023}<p,q<2^{1024}$, with
known $N=pq$ satisfying $2^{2047}<N<2^{2048}$.
There exists a quantum algorithm that returns a factor
$d\in\{p,q\}$ with probability at least $0.99$, using at most
$4097$ logical qubits,
$1.18\times10^{17}$ Toffoli gates,
$4.17\times10^{14}$ CNOT gates,
$1.49\times10^8$ single-qubit gates,
$1.18\times10^{17}$ quantum computation time,
$132$ GB of classical memory,
and $1.54\times10^{19}$ classical 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
Let $m,n\geq0$, $1\leq N\leq2^n$, and $0\leq a<N$
be integers with $\gcd(a,N)=1$.
There exists a reversible quantum circuit
on $m+3n$ qubits, using at most $2n$ ancilla qubits,
$24mn\left((3744n+624)\lceil\log_2(n+1)\rceil+160n+65\right)+3n$ Toffoli gates, $24mn^2\left(39\lceil\log_2(n+1)\rceil+2\right)+n$ CNOT gates, and $2$ single-qubit gates,
whose action on computational basis states satisfies
$$
U_{N,a}\ket{z}\ket{y}
=\ket{z}\ket{y\oplus(a^z\bmod N)}
$$
for every $z<2^m$ and $y<2^n$.
Let $N\geq2$ and $x$ be integers with $\gcd(x,N)=1$,
$r$ be the least positive integer satisfying $x^r\equiv1\pmod N$,
$n=\lceil\log_2N\rceil$, and $t=\lceil\log_2(N^2)\rceil$.
Given access to a $(t+n)$-qubit 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 probability at least $\varphi(r)/(3r)$,
using at most $t+n$ logical qubits, 1 query to $U_x$,
$t(t-1)+3\lfloor t/2\rfloor$ CNOT gates,
$t(3t+1)/2$ single-qubit gates,
$12t+11n+17$ classical bits,
and $12t^2+4nt+64t+4n+57$ classical operations.
Let $N\geq2$ and $x\geq0$ be integers with $\gcd(x,N)=1$,
$r$ be the least positive integer satisfying $x^r\equiv1\pmod N$,
$n=\lceil\log_2N\rceil$, and $q=2^t$ be a multiple of $r$
for an integer $t\geq1$.
Given access to a $(t+n)$-qubit 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\}$ with probability one,
using at most $t+n$ logical qubits, 1 query to $U_x$,
$t(t-1)+3\lfloor t/2\rfloor$ CNOT gates,
and $t(3t+1)/2$ single-qubit gates.
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}\!\left[\,O\,U_\theta\,A\,U_\theta^{\dagger}\,\right],$ 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}\left((a\ket{0}+b\ket{1})\ket{\psi}\right)
=
(a\ket{0}+e^{i\phi}b\ket{1})\ket{\psi}.
$$
Polynomial transformation on block encodings (Hermitian, real with parity)
Let $m,n,L\geq0$ be integers,
$P=\sum_{j=0}^{L}c_jx^j$ be a degree-$L$ real polynomial
with parity $L\bmod2$ such that $|P(x)|\leq1$ for every
$x\in[-1,1]$, and $U$ be a $(1,m,0)$-block-encoding
of an $n$-qubit Hermitian matrix $A$.
Given access to $U$ and $U^\dagger$, there exists
a quantum circuit $\mathcal V$ that implements
a $(1,m+1,0)$-block-encoding of
$P(A)=\sum_{j=0}^{L}c_jA^j$, using at most
1 ancilla qubit, $L$ queries to $U$ and $U^\dagger$,
$192mL$ CNOT gates, and $((296m+3)L+2)$ single-qubit gates.
$P$
Polynomial applied to the encoded Hermitian matrix.
Polynomial transformation on block encodings (Hermitian)
Let $m,n,L\geq0$ be integers,
$P=\sum_{j=0}^{L}c_jx^j$ be a degree-$L$ complex polynomial
such that $|P(x)|\leq1$ for every $x\in[-1,1]$,
and $U$ be a $(1,m,0)$-block-encoding
of an $n$-qubit Hermitian matrix $A$.
Given access to $U$, $U^\dagger$ and controlled-$U$,
there exists a quantum circuit $\mathcal V$ that implements
a $(4,m',0)$-block-encoding of
$P(A)=\sum_{j=0}^{L}c_jA^j$ for $m\leq m'\leq m+3$,
using at most 3 ancilla qubits,
$L$ queries to $U$ and $U^\dagger$,
1 query to controlled-$U$,
$((192m+6)L+6)$ CNOT gates,
and $((296m+6)L+13)$ single-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.
Let $p>3$ be prime, $E/\mathbb F_p$ be a short Weierstrass
elliptic curve, $P\in E(\mathbb F_p)$ be a known point
of known prime order $r$, $Q\in\langle P\rangle$ be a known
point other than the point at infinity, and $0<\eta\leq1$.
Set $f=\lceil\log_2p\rceil$, $t=\lceil\log_2(12r)\rceil$,
and $k=\lceil\log\eta/
\log(1-r(r-1)/2^{2t+2})\rceil$.
Given access to an oracle $U_{P,Q}$ satisfying
$U_{P,Q}\ket{a,b,R}=\ket{a,b,R+[a]P-[b]Q}$,
there exists a quantum algorithm that returns
$m\in\{0,\ldots,r-1\}$ satisfying $Q=[m]P$
with probability at least $1-\eta$, using at most
$2t+2f+1$ logical qubits,
$k$ queries to $U_{P,Q}$,
$k(2t^2+4t+6\lfloor t/2\rfloor)$ CNOT gates,
$k(3t^2+25t+4f+3)$ single-qubit gates,
$2t+2f+2+k\left(5t^2+248ft+721t+8f+6\lfloor t/2\rfloor+125\right)$
quantum computation time,
$\max\{18t^2+70t+70,18f^2+72f+69\}+6f+4t+8$
classical bits,
and $k(248ft+686t+119)+1$ classical operations.
Let $0<\eta<1$ and
$k=\lceil\log(\eta/2)/\log(147/256)\rceil$.
For all sufficiently large integers $n$, set
$\ell=\lfloor(n+2)/2\rfloor$ and suppose $(p,q)$ is drawn
uniformly from the ordered pairs of distinct primes satisfying
$2^{n-1}<p,q<2^n$, with known $N=pq$ satisfying
$2^{2n-1}<N<2^{2n}$.
Given access to oracles $V_{N,g,x}$ satisfying
$V_{N,g,x}\ket{a,b,y}
=\ket{a,b,y\oplus(g^a x^{-b}\bmod N)}$
for units $g,x$ modulo $N$, there exists a quantum algorithm
that returns a factor $d\in\{p,q\}$ with probability
at least $1-\eta$, using at most
$3n+2\ell+1$ logical qubits,
$16k$ queries to $V_{N,g,x}$,
$16k\left(n^2+2n\ell+2\ell^2+n
+3\lfloor(n+\ell+1)/2\rfloor+3\lfloor\ell/2\rfloor\right)$
CNOT gates,
$k(24n^2+48n\ell+48\ell^2+107n+98\ell+49)-3n-2\ell-1$
single-qubit gates,
$k\left(40(n+\ell)^2+56(n+\ell)+113\right)-1$
quantum computation time,
$880803934n+293601328\ell+587202961$ classical bits,
and $k(2^{52}n+1)$ classical operations.
Suppose $p$ and $q$ are unknown distinct primes and $N=pq$
is known. Let $n=\lceil\log_2N\rceil$, $0<\eta\leq1$,
and $k=\lceil\log\eta/\log(1-1/(48n))\rceil$.
Given access to modular-exponentiation oracles $U_{N,a}$
satisfying $U_{N,a}\ket{z,y}
=\ket{z,y\oplus(a^z\bmod N)}$,
there exists a quantum algorithm that returns a factor
$d\in\{p,q\}$ with probability at least $1-\eta$,
using at most $3n$ logical qubits,
$k$ queries to $U_{N,a}$,
$k(4n^2+n)$ CNOT gates,
$k(6n^2+4n)$ single-qubit gates,
$3n+k(66n^2+232n+317)+2$ quantum computation time,
$k(22n+1)+70n+42$ classical bits,
and $k(56n^2+222n+316)+2$ classical operations.
Let $d,m,N$ be positive integers, $B,t\geq0$,
$H_1,\ldots,H_m\in\mathbb{C}^{d\times d}$ be Hermitian
matrices with $\|H_j\|\leq B$, and $h_1,\ldots,h_m\geq0$
satisfy $\lambda=\sum_{j=1}^{m}h_j>0$.
Set $p_j=h_j/\lambda$ and $T=t\lambda$, and define
$E(X)=\sum_{j=1}^{m}p_j e^{-i(T/N)H_j}X e^{i(T/N)H_j}$
and
$U(X)=e^{-i(T/N)\sum_{j=1}^{m}p_jH_j}
X e^{i(T/N)\sum_{j=1}^{m}p_jH_j}$
for $X\in\mathbb{C}^{d\times d}$.
Then
$$
\|U^N-E^N\|_{1\to1}
\leq
B^2\left(e^{TB}(2+TB)+2\right)\frac{T^2}{N},
$$
where powers denote repeated composition,
$\|M\|=\sup\{\|Mv\|_2:v\in\mathbb{C}^d,\ \|v\|_2\leq1\}$,
$\|X\|_1=\operatorname{Tr}\sqrt{X^\dagger X}$,
and
$\|\Phi\|_{1\to1}=\sup_{\|X\|_1\leq1}\|\Phi(X)\|_1$.
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}\!\left(\langle H_jH_k\rangle-\langle H_j\rangle\langle H_k\rangle\right)=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\geq1$, $N=2^n$ and $\omega=e^{2\pi i/N}$.
There exists an $n$-qubit quantum circuit using at most
$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^{jk}\ket{k}.
$$
$\mathtt{QFT}_{N}$
Quantum Fourier transform over N computational-basis states.
$\omega$
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}$,
for every integer $n_a\geq1$, there exists a quantum algorithm
that estimates $\theta$ modulo $1$ up to precision $2^{-n_a}$
and failure probability at most $1-4/\pi^2$,
using at most $n_a$ ancilla qubits,
$2^{n_a}-1$ queries to controlled-$U$,
$n_a(n_a-1)+3\lfloor n_a/2\rfloor$ CNOT gates,
and $n_a(3n_a+1)/2$ single-qubit 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.
Let $d\geq 0$. There exists a sequence of phase factors
$\Phi=(\phi_0,\ldots,\phi_d)\in\mathbb{R}^{d+1}$ such that,
for every $x\in[-1,1]$,
$$
U_\Phi(x)
=
e^{i\phi_0 Z}\prod_{j=1}^{d}\left(
\begin{bmatrix}
x & -\sqrt{1-x^2}\\
\sqrt{1-x^2} & x
\end{bmatrix}e^{i\phi_j Z}\right)
=
\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]$.
At $d=0$, the degree condition on $Q$ means $Q=0$.
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}\left(R_Z(x)\,R_Y(\theta_j)R_Z(\phi_j)\right)
=
\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}$.
Let $n\geq1$, $N=2^n$, $\omega=e^{2\pi i/N}$,
and $\ket{\psi}=\sum_{j=0}^{N-1}\alpha_j\ket{j}$
be an $n$-qubit state.
There exists an $n$-qubit quantum circuit using at most
$n$ Hadamard gates, $n(n-1)/2$ single-qubit phase gates and $n$ classical bits to
obtain a classical output $k\in\{0,\ldots,N-1\}$ with distribution
$$
\Pr[k]
=
\frac{1}{N}
\left|\sum_{j=0}^{N-1}\alpha_j\omega^{jk}\right|^2.
$$