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?

  • $\begingroup$ What is the question you are asking? Could you share what you have tried so far? $\endgroup$
    – 3yakuya
    Jan 3, 2022 at 19:05
  • 1
    $\begingroup$ I updated the question. $\endgroup$
    – Tom Clancy
    Jan 3, 2022 at 19:19
  • 1
    $\begingroup$ 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! $\endgroup$ Jan 3, 2022 at 23:23

1 Answer 1


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.


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.