Consider a constant depth $1\text{D}$ quantum circuit, which is applied to the input state $|0^{n}\rangle$, and whose output is measured in the standard basis. You can assume that the gates of the circuit come from a fixed universal gate set, like $\{\text{Toffoli}, \text{Hadamard} \}$.

Let $p_{x_1}$ be the marginal probability of the first bit of the output. Is it true that \begin{equation} p_{x_1} = \frac{1}{2} \pm c, \end{equation} for some $0 \leq c \leq \frac{1}{2}$ that has no dependence on $n$, but that depends on the gates used and the depth of the circuit?

An observation (which might be relevant) is to note that the backward lightcone of the first bit is of a constant size. Hence, only a constant fraction of the inputs "influence" what happens to the first bit. For every given constant depth circuit, we can cleave out a different quantum circuit, having a constant number of inputs and a constant number of gates such that the marginal probability of the first bit is same for both circuits. Since there is no dependence of $n$ in the second circuit, is this sufficient to conclude what I want?

  • $\begingroup$ Are you meaning to ask that there's a $c$ that depends only on the depth of the circuit, and not the nature of the circuit itself? Otherwise, your question seems kind of odd - for any computation, there is a probability of a given outcome for the first qubit, and that probability is between 0 and 1, and therefore there's a c which is upper bounded by 1/2. $\endgroup$
    – DaftWullie
    Jun 21 at 6:54
  • $\begingroup$ Yes, what I mean to say is that there is a $c$ that only depends on the depth of the circuit and is not a function of $n$. $\endgroup$
    – BlackHat18
    Jun 21 at 8:00
  • $\begingroup$ If you do nothing to the first qubit then $p_{x_1}=0$ and $c=\frac{1}{2}$ (assuming by $p_{x_1}$ you mean the probability of observing the first bit to be "1"). Or you can apply an $X$ with constant depth to get $p_{x_1}=1$ but that depth depends only on your gateset. Regarding the lightcone comment, reducing the purity of the local system (qubit 1) by entanglement is sufficient but not necessary to reduce $c$ and send $p_{x_1}\rightarrow \frac{1}{2}$, so maybe you want to modify your question to make that lightcone comment more relevant? $\endgroup$
    – forky40
    Jun 21 at 18:42
  • $\begingroup$ I updated the question with more details. $\endgroup$
    – BlackHat18
    Jun 22 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.