3
$\begingroup$

I'm trying to find a way to check if a given quantum circuit is essentially a classical one (up to changes in phase).

Given a description of a quantum circuit by a list (of size $l$) of ordered operations of Hadamard gates and Toffoli gates (i.e, specifying the specific qubits on which they are operated) operating on $n$ qubits, is there an efficient (polynomial in $l,n$) algorithm that finds whether the computation of the circuit on a quantum state which is not a superposition?

That is, check if for $\forall x \in\{0,1\}^n \ \exists y\in\{0,1\}^n$ such that $U|x⟩=|y⟩$, for $U$ that is represented by the given list.

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ If you care about computational complexity, then deterministic doesn't really imply "effectively classical", because the corresponding classical permutation operator might be exponentially deep in $n$. $\endgroup$
    – tparker
    Commented Apr 22, 2020 at 23:45
  • 2
    $\begingroup$ What necessary and/or sufficient conditions have you explored? No Hadamard, no problem. Two Hadamards in a row to the same qubit, no problem. Anything else? $\endgroup$
    – Mark Spinelli
    Commented Apr 23, 2020 at 3:55
  • 1
    $\begingroup$ @MarkS odd number of Hadamards in the circuit => cannot be a permutation? $\endgroup$
    – DaftWullie
    Commented Apr 23, 2020 at 7:41
  • 1
    $\begingroup$ Presumably your condition $U|x\rangle=|y\rangle$ should allow for an arbitrary phase on the $|y\rangle$? $\endgroup$
    – DaftWullie
    Commented Apr 23, 2020 at 7:42
  • 1
    $\begingroup$ Just idea: If you apply the circuit on all states from computational basis and only these states are returned (in different order, of course), i.e. there is no superposition, then the circuit implements some classical logical function as it maps $\{0,1\}^n$ to $\{0,1\}^n$. Assume the circuit is described by a matrix $U$ then to be classical is equivalent to conditions that there is only one 1 in each column and row of $U$ and other elements are zeros. Does it make sense? $\endgroup$
    – Martin Vesely
    Commented Apr 23, 2020 at 10:14

2 Answers 2

Reset to default
3
$\begingroup$

This is at least NP hard. The basic problem is that the circuit can encode things like "if the first N qubits encode a computational basis solution to the hard-coded 3-SAT problem X then apply Hadamards to the remaining qubits, otherwise do nothing". Deciding whether such a circuit is classical-ish requires determining if the 3-SAT problem it encodes is satisfiable or not.

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

Following up on @Martin's suggestions, there might be a $\mathsf{BQP}$ algorithm to test for what you want, as long as you allow for your input circuit $U$ to be only "close to" a classical permutation matrix, that is, "close to" having a $1$ in each row/column.

For example, let $\vert x\rangle$, $\vert y\rangle$ be computational basis states, and let $\vert w\rangle$ be some monkey state (perhaps also in superposition).

We have $U\vert x\rangle=\alpha\vert y\rangle+\beta\vert w\rangle$. As long as $\alpha^2\gg\beta^2$ for each computational basis, we can choose random computational basis $\vert x\rangle$, apply $U\vert x\rangle$, and measure a small number of times.

If we always measure the same $y$ for the same input $\vert x\rangle$, and never $w$, then we can conclude, at least for that basis state $\vert x\rangle$, that $\alpha^2\gg \beta^2$; that is, the $x$ row of $U$ has a single $1$ at the $y$ column.

We can repeat to amplify, by choosing another basis state. I don't think we need to explore a lot of the $2^n$ states to get some confidence that $U$ is effectively a permutation matrix.

I think if you want to do a lot better than this, you might run against the BBBV-theorem, because you'd be looking for a tagged input (unless there are classical tests about the number of Hadamard's like described in the comments.)

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ I'm not sure I agree with the sentence "I don't think we need to explore a lot of the 2𝑛 states to get some confidence that 𝑈 is effectively a permutation matrix". What prevent's my unitary to behave "nicely" on a polynomial amount of $x$'s (that I check) but behave totally different for all the other inputs? $\endgroup$
    – GWB
    Commented Apr 23, 2020 at 14:07
  • $\begingroup$ Let $N=2^n$. Suppose your $N\times N$ circuit $U$ has only a polynomial (in $n$) number of "nice" inputs. Call the set of "nice" inputs $A$. If you randomly choose test sates $\vert x\rangle$, then there is a superpolynomial (exponential) likelihood that at least one of your inputs will not be in $A$, and hence that $U\vert x\rangle$ will measure $w$ at least once. It's the same Chernoff-bound reason why most $\mathsf{BPP}$ and $\mathsf{AM}$ works, right? $\endgroup$
    – Mark Spinelli
    Commented Apr 23, 2020 at 14:21
  • $\begingroup$ You're right about the "nice" inputs, so I suppose that problem is when there're only polynomially "bad" inputs (for which s 𝛼 and 𝛽 are not far from each other), so you can't "catch" them by sampling random input. $\endgroup$
    – GWB
    Commented Apr 23, 2020 at 14:43
  • $\begingroup$ Yes! Exactly. But if there's only a polynomial number of "bad" inputs for which $\alpha$ and $\beta$ are not far from each other, then the BBBV theorem precludes an efficient algorithm, I think. $\endgroup$
    – Mark Spinelli
    Commented Apr 23, 2020 at 15:07

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.