# Implementing "computable phase shifts" using T Toffoli ( problem 4.1 from Nielsen and Chuang's)

I am reading/studying the famous Nielsen and Chuang's book and ran into this interesting question and I don't quite understand the $$f(x)$$. It says it simply maps from $$m$$ to $$n$$ bits. But don't we have to know what $$f(x)$$ is to build a circuit using Ts and CNOTs? I think I miss something here.

Thanks.

Problem 4.1: (Computable phase shifts) Let $$m$$ and $$n$$ be positive integers. Suppose $$f:\left\{0, \ldots, 2^{m}-1\right\} \rightarrow\left\{0, \ldots, 2^{n}-1\right\}$$ is a classical function from $$m$$ to $$n$$ bits which may be computed reversibly using $$T$$ Toffoli gates, as described in Section 3.2.5. That is, the function $$(x, y) \rightarrow(x, y \oplus f(x))$$ may be implemented using $$T$$ Toffoli gates. Give a quantum circuit using $$2 T+n$$ (or fewer) one, two, and three qubit gates to implement the unitary operation defined by $$|x\rangle \rightarrow \exp \left(\frac{-2 i \pi f(x)}{2^{n}}\right)|x\rangle .$$

• Have you thought about treating $f$ as a black box? For example can you treat $f$ abstractly and construct a circuit of $2T+n$ qubit gates to convert the values of $f$ into phases and use those to conditionally rotate the amplitude of $\vert x\rangle$? Feb 1, 2022 at 22:16
• @MarkS I will think about it. Thanks! Feb 2, 2022 at 2:21

1. Compute $$\hat P|x,y\rangle \equiv |x,y \oplus f(x)\rangle$$ using $$T$$ Toffoli gates.
2. Expand $$q=\sum\limits_{j=0}^{n-1} q_j 2^j$$ with $$q_j$$ being the digits of a binary representation of $$0\le q\le 2^{n-1}$$.
3. Now observe that \begin{align*} \hat O|x,q\rangle&\equiv\mathrm e^{2\pi\mathrm iyn/2^n}\prod\limits_{j=0}^{n-1}\exp\left(-\pi\mathrm i q_j2^{j-n+1}\right) \Bigg|x,q\bigg\rangle \\ &= \exp\left(-2\pi\mathrm i/2^n\left(\sum\limits_{j=0}^{n-1}q_j2^j-y\right)\right) \Bigg|x,q\bigg\rangle \\ &= \exp\left(-2\pi\mathrm i/2^n\left(q-y\right)\right) |x,q\rangle, \end{align*} so that for $$q = y\oplus f(x)$$, we obtain $$\hat O|x,y\oplus f(x)\rangle=\exp\left(-2\pi\mathrm i/2^nf(x)\right)|x,y\oplus f(x)\rangle.$$ The operation $$\prod\limits_{j=0}^{n-1}\exp\left(-\pi\mathrm i q_j2^{j-n+1}\right)$$ can be implemented using $$n$$ single-qubit phase gates $$\hat U_{n-1}\cdots\hat U_0$$ each acting as $$\hat U_j=\begin{pmatrix}1&0\\0&\mathrm e^{-\pi\mathrm i 2^{j-n+1}}\end{pmatrix}$$ while the global $$y$$-dependent phase can be neglected.
4. Uncompute $$\hat P^\dagger|x,y \oplus f(x)\rangle = |x,y\rangle$$, using $$T$$ Toffoli gates.
The total cost of the operation $$\hat P^\dagger\hat O\hat P$$ therefore is $$2T+n$$ gates, as required.