Timeline for How to check if a quantum circuit is deterministic?
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 23, 2020 at 15:07 | comment | added | Mark Spinelli | 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. | |
| Apr 23, 2020 at 14:43 | comment | added | GWB | 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. | |
| Apr 23, 2020 at 14:21 | comment | added | Mark Spinelli | 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? | |
| Apr 23, 2020 at 14:07 | comment | added | GWB | 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? | |
| Apr 23, 2020 at 13:46 | history | answered | Mark Spinelli | CC BY-SA 4.0 |