Let us be given the description of a quantum circuit $\mathsf{Q}$, acting on $n$ qubits, such that

\begin{equation} \langle 0^n|\mathsf{Q}|0^n\rangle = \frac{\#0_f - \#1_f}{\sqrt{2^n}}, \end{equation} for some Boolean function $f : \{0, 1\}^n \rightarrow \{0, 1\}$, where $\#0_f$ and $\#1_f$ are the number of inputs for which $f$ evaluates to $0$ and $1$ respectively.

Let's say one could find a description of $f$ when given a description for $\mathsf{Q}$. Now, is there a way to efficiently construct the circuit $\mathsf{Q_k}$ such that the amplitudes of $\mathsf{Q_k}$ look like \begin{equation} \frac{\#0_f - \#1_f~+k}{\sqrt{2^n}}, \end{equation} for some constant integer $k$?

In this paper (page $10$), it is mentioned that this is what is termed a "padding argument," and the paper seems to contend that this can be done by using "$k$ additional inputs." But it wasn't immediately clear to me how to do this.


1 Answer 1


In the paper that above question references, it is assumed that we are given a classical circuit $C$ which computes the function $f: \{0,1\}^n \rightarrow \{0,1\}$ and an another classical algorithm which takes $C$ as the input and outputs a diagonal quantum circuit $Q$ which uses $\mathrm{T} = $ poly$(n,|C|)$ qubits such that

\begin{align} \langle 0^n|Q|0^n\rangle = \frac{\#0_f - \#1_f}{2^T} \end{align}

The author of the paper claims that you can modify the circuit $C$, not $Q$, by adding $k$ additional input (by the increasing the domain size by $k$, not the number of input bits) to make a new circuit $C[k]$ such that $C(x) = 1$ for $x$ in the newly added domain. Now you can pass this new circuit to the classical algorithm which converts into a quantum circuit $Q_k$ as the question asks.

  • $\begingroup$ How can you modify $C$ without adding extra input bits? $\endgroup$
    – Tom Clancy
    Oct 4, 2022 at 19:54
  • $\begingroup$ In general, you do need to add extra bits to modify the circuit $C$. $\endgroup$
    – Chaithanya
    Oct 5, 2022 at 5:18
  • $\begingroup$ Could you provide a sketch of how in your answer? $\endgroup$
    – Tom Clancy
    Oct 6, 2022 at 6:02

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.