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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.