# Question regarding the output probability of a quantum circuit

Consider a quantum circuit $$\text{Q}$$, run on $$|0^{n}\rangle$$. For a specific $$x \in \{0, 1\}^{n}$$, let's say we are interested in the probability

$$p_x = |\langle x|~\text{Q}~|0^{n}\rangle|^{2}.$$

Now, consider the set $$S=\{1, 2, \ldots, n\}.$$

Partition the set into $$A$$ and $$\bar{A}$$ such that $$A \cup \bar{A} = S$$ and $$A\cap\bar{A}=\emptyset$$ .

What is a proof that $$p_x$$ can be written as

$$p_x = \sum_{a} c_{x_A}^{a} c_{x_\overline{A}}^{a},$$

for some choices of complex numbers $$\{ c_{x_A}^{a} \}$$ and $$\{ c_{x_\bar{A}}^{a}\}?$$

I got this decomposition on page 6 (in the proof of Theorem 1) of this paper.

According to the paper, $$x_A$$ is the value of $$x$$ when restricted to the set $$A$$.

Here's what I have tried. Note that if the output qubits labelled by regions $$A$$ and $$\bar{A}$$ are not connected by any entangling gates, the fact that such a decomposition exists is trivial. I presume the summation indicates that, in general, there will be entangling gates. But, I am not sure how that implies a sum of products. Maybe something to do with a path integral approach?

• What is the question you are asking? Could you share what you have tried so far? Jan 3 at 19:05
• I updated the question. Jan 3 at 19:19
• You have four different subscripts/superscripts in the same equation that you aren't explaining. What is c? what is a? What is x? What is a being summed over? How is c related to your choice of subsets? Is the choice of subsets allowed to vary based on x? There's not enough information here! Jan 3 at 23:23

Let $$\mathcal{H}_A$$ denote the Hilbert space of qubits in partition $$A$$ and similarly for $$\mathcal{H}_\bar{A}$$. Define the operator $$P:=Q|0^n\rangle\langle 0^n|Q^\dagger$$ and write its Schmidt decomposition

$$P = \sum_a R_a\otimes Q_a\tag1$$

where $$R_a$$ are operators on $$\mathcal{H}_A$$ and $$Q_a$$ are operators on $$\mathcal{H}_\bar{A}$$. See for example the answer to this question for more details about Schmidt decomposition for operators.

Finally, write

\begin{align} p_x&=|\langle x|Q|0^n\rangle|^2\tag2 \\ &= \langle x|Q|0^n\rangle\langle 0^n|Q^\dagger|x\rangle\tag3 \\ &= \langle x|P|x\rangle\tag4 \\ &= \langle x_A|\otimes\langle x_\bar{A}|\left(\sum_a R_a\otimes Q_a\right)|x_A\rangle\otimes|x_\bar{A}\rangle\tag5 \\ &= \sum_a \langle x_A|R_a|x_A\rangle\langle x_\bar{A}|Q_a|x_\bar{A}\rangle\tag6 \\ &= \sum_a c_{x_A}^a c_{x_\bar{A}}^a\tag7 \end{align}

where we defined $$c_{x_A}^a:=\langle x_A|R_a|x_A\rangle$$ and $$c_{x_\bar{A}}^a:=\langle x_\bar{A}|Q_a|x_\bar{A}\rangle$$.

The fact that $$a$$ ranges over the Schmidt decomposition of $$Q$$ confirms the intuition that the sum has more than one term when $$Q$$ entangles the partitions and one term otherwise.