6
$\begingroup$

Suppose you are given two circuit descriptions $A$ and $B$ where by a circuit description I mean a sequence of gates (in the order they are applied) and the qubits they are applied on. (For the sake of simplicity lets have the number of qubits fixed to $n$ and the circuit is measured in the computational basis).

Are there techniques to check from the circuit descriptions $A,B$ that the sampled output probability distributions induced by the computational basis measurements are

  • a) equal

  • b) more interesting to me: $\epsilon$-close in total variation distance

Even more ambitious, are there results about the complexity of this task? Are there such results for classical boolean circuits?

To clarify, if the circuit descriptions would only differ in the sequence of gates and not otherwise, i.e. each gate is replaced by a different gate but the positions of the gates in the circuit (the architecture) are the same in $A,B$, then it is known that operator norm errors $||U_j-V_j||=\epsilon_j$ of the individual gates just add up.

A "brute-force" way to solve this question is of course to classically simulate the output states of both circuits (by say a tensor network contraction) and compare those but this is certainly exponential time, so I am looking for smarter approaches.

Improve this question
$\endgroup$
2

2 Answers 2

Reset to default
0
$\begingroup$

A common method is the diamond norm, which is taking 2 operations (you can translate the whole circuit to 1 big matrix operation) and looking for the case of density matrix that will return the maximal value between them:

enter image description here

Refer to it in Wikipedia

Improve this answer
$\endgroup$
0
$\begingroup$

Sam's link to the posting on tcs answers the OP's question - but here's some other comments that were hinted at here and there.

  • The exact classical problem is coNP-complete as this reduces to TAUTOLOGY. This implies that under the very reasonable assumption that NP$\ne$coNP, there's not even a small witness to two polynomial-size circuits being equal to each other.
  • Depending on $\epsilon$, a classical version which allows for some slack is (I think) coAM-complete - two circuits that have almost exactly the same truth table can't even be easily certified as such.
  • The exact quantum problem is coNQP-complete. But I think there might be a lot of dependence on the specific gate-set allowed.
  • Thus I agree it's more natural to think of the $\epsilon$-version, which is coQMA-complete.

All of these classes are pretty tough - but if you're only interested in how two circuits act on a specific fiducial basis state that you can prepare at-will, say $|\psi\rangle=|00\cdots0\rangle$, then certainly you can prepare and measure $B^\dagger A|\psi\rangle$ and confirm it reverts to the all zeroes ket.

If we consider arithmetic circuits instead of classical or quantum circuits, this problem is related to polynomial identity testing, and the Scwartz-Zippel lemma is very powerful.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Would you really compare $A|\psi\rangle$ and $B|\psi\rangle$, or $B^\dagger A|\psi\rangle$ and $|\psi\rangle$ (because it means just measuring the first state in the standard basis)? $\endgroup$
    – DaftWullie
    Nov 27 at 13:30
  • $\begingroup$ @DaftWullie yeah I guess you're right. Indeed if your fiducial state $|\psi\rangle$ is a basis-state such as all-zeroes then you don't even need two separate registers - just execute $B^\dagger A|00\cdots0\rangle$ and measure to see if it reverts back to the all-zeroes ket. I got tripped up on this in thinking about obfuscating the identity, which is likely a harder problem than finding peaked circuits. $\endgroup$
    – Mark Spinelli
    Nov 27 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.