1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Well, you cannot really know. Given input and output states you can try to reconstruct the quantum process and then try to implement it. However, this is black box learning and it does not tell you anything about the inner workings of the circuit. Two circuits might be related by symmetries or simply do the same job, albeit, one of them to do it much more efficiently (i.e. to be a shallower circuit with less number of gates etc). The circuit it self is not as important as the actual operation that is supposed to be performed using those circuits and that can definitely be reconstructed. $\endgroup$
    – Marion
    Commented Apr 15, 2022 at 11:17
  • $\begingroup$ @Stare100 - Classically, given two boolean functions $f$ and $g$ acting on the same number of bits, both presented as black-boxes, how could you learn whether $f=g$? This is polynomial identity testing and the Schwartz-Zippel lemma. Your putative algorithm is basically the same as PIT but I'm pretty sure it's far from efficient quantumly, although if you know from when your circuits $X$ and $Y$ are drawn you might have some luck. $\endgroup$ Commented Apr 15, 2022 at 13:56

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ +1 but have you thought about how many different basis states $z_i$ will need to be tested to conclude that $\hat X=\hat Y$ with high confidence? I think it's way worse than what we can do classically. That is I think there are way too many circuits that are "inverses" of each other for a handful of basis states but are otherwise completely unrelated. $\endgroup$ Commented Apr 15, 2022 at 16:27
  • $\begingroup$ Right - my answer is applicable only when we care only about the similarity of our circuits with respect to a particular reference state - often true in my work with variational algorithms, but certainly not in general! $\endgroup$
    – jecado
    Commented Apr 15, 2022 at 16:49
2
$\begingroup$

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.

$\endgroup$

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.