Best way to measure similarity of two quantum circuits?

Question

Suppose you have some unknown circuit X. You don't know the structure of circuit X, but you do have a set of inputs and corresponding outputs, i.e. you know what the circuit does. Then suppose you have another circuit, circuit Y, where you have both inputs and outputs, and circuit structure. What's the best way to determine how close the structure of circuit Y is to that of circuit X? One idea I've tried so far is to compare the output vectors of the two circuits (using something like taking the norm of the difference of each pair of output vectors). Is there perhaps a better solution?

Answer 1

This answer is for a more restricted case than in the original question, when our knowledge of unitaries $\hat X$ and $\hat Y$ applies to a single input reference state in the computational basis $|z_0⟩$.

---

We know that $\hat X|z_0⟩=|Ψ_X⟩$, and that $\hat Y|z_0⟩=|Ψ_Y⟩$. As the OP suggested, one measure of the similarity of $\hat X$ and $\hat Y$ is to compare the two output vectors. We can obtain the overlap $|⟨Ψ_Y|Ψ_X⟩|^2$ with a fairly straightforward procedure.

Let's say we start with a quantum computer in the state $|Ψ_X⟩$, and we know enough about $\hat Y$ to construct its quantum circuit. We can also construct the inverse of $\hat Y$ (ie. $\hat Y^†$) by inverting each gate in its quantum circuit and reversing the order.

We can prepare the quantum state $|Ψ'⟩=\hat Y^† |Ψ_X⟩$ by applying the circuit for $\hat Y^†$ to the quantum state $|Ψ_X⟩$, and then we can measure $|Ψ'⟩$ in the computational basis. Let $p_0$ be the empirical probability of measuring the basis state $|z_0⟩$, which should converge to $|⟨z_0|Ψ'⟩|^2$ for enough measurements. Expanding this quantity, $$ p_0 \rightarrow |⟨z_0|Ψ'⟩|^2 = |⟨z_0|\hat Y^† |Ψ_X⟩|^2 = |⟨Ψ_Y|Ψ_X⟩|^2$$ Therefore, $p_0$ estimates the desired overlap.

---

For further intuition: we have "computed" $\hat X$, and then we "uncompute" $\hat Y$. If $\hat X$ and $\hat Y$ are similar (with respect to this one reference state!), the "uncomputation" should return us exactly to the original reference state. The extent to which it hasn't returned us to the original reference state tells us the extent to which $\hat X$ and $\hat Y$ are not similar.

Answer 2

Although @jecado and the OP are right in that you can test a handful of basis states, in general it is QMA-complete to test for circuit identity for all such states, as Janzing, Wocjan, and Beth provide in Identity check is QMA-complete.

From their abstract:

Given two descriptions of quantum circuits and a description of a common invariant subspace, decide whether the restrictions of the circuits to this subspace almost coincide. We show that equivalence check is also in QMA and hence QMA-complete.

I haven't studied the paper in any detail - the introduction looks very readable, but I think this shows that the generalization to the OP's question is likely outside of anything that can be done efficiently.