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!

]]>