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.


1 Answer 1


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


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.