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.


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

  • 1
    $\begingroup$ 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$? $\endgroup$ Feb 1, 2022 at 22:16
  • $\begingroup$ @MarkS I will think about it. Thanks! $\endgroup$ Feb 2, 2022 at 2:21

1 Answer 1


One possible way would go as follows:

  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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.