I think I misunderstood you earlier and was looking for inapproximability of *unitaries* using arbitrary gates. It seems you meant approximability of some bigger class of operators with arbitrary gates. I was excluding results that don’t have “unitary” or “quantum”. I also suspect that you meant Warren’s theorem. (Replacing Waring with Warren gives better results).

Your paper is what I am looking for, thanks for the pointer!

]]>I am very interested in finding that proof. I am guessing the link you posted is for the theorem not the proof (the text makes no mention of unitaries, the theorem is used for lower bounds on algebraic decision trees).

I tried googling “waring” with a bunch of keywords (unitary, approximate, quantum, gates, ..etc.) to no avail. Do you, by any chance, recall some resource that has that proof (or some non-obvious keywords, like the author that would help me find it)?

Thanks again!

]]>I have a small question. On page 125, it says:

“In fact, a little algebraic geometry (which we won’t go into here) is enough to show that exponentially many gates are needed to approximate most n-qubit unitaries as well, or even most n-qubit diagonal unitary transformations.”

Are you referring to the result proven in [Knill 95]? If yes, on the surface the proof given is not algebraic geometric. Are you refering to another result or is there a nicer proof of the same result elsewhere?

[Knill 95] https://arxiv.org/abs/quant-ph/9508006

]]>