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.
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.
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.
$$
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.
$$
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.
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.
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}.
$$
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$.
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.
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.
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.
$$
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.
$$
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.
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.
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.
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$.
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}$.