I posted/tweeted about that elsewhere a couple a weeks ago: *Quantum Computers Speed Up Classical with Probability Zero* Yuri Ozhigov https://arxiv.org/abs/quant-ph/9803064
also by Ozhigov: *Constructive physics* Yuri Ozhigov https://arxiv.org/abs/0805.2859 - pt On Monday, October 22, 2018 at 5:40:17 PM UTC-5, Brent wrote: > > I can't find it right now, but I think I read that someone had proven > that the number problems that could be speeded up by quantum computation > was of measure zero. Of course the number of problems we're interested > in is also of measure zero, so that's not necessarily an argument > against developing quantum computers. > > Brent > > On 10/21/2018 6:44 AM, Telmo Menezes wrote: > > Finally a proof that quantum computers outperform classical computers > > for a certain class of problems? Thoughts? > > > > "Quantum computers are expected to be better at solving certain > > computational problems than classical computers. This expectation is > > based on (well-founded) conjectures in computational complexity > > theory, but rigorous comparisons between the capabilities of quantum > > and classical algorithms are difficult to perform. Bravyi et al. > > proved theoretically that whereas the number of “steps” needed by > > parallel quantum circuits to solve certain linear algebra problems was > > independent of the problem size, this number grew logarithmically with > > size for analogous classical circuits (see the Perspective by > > Montanaro). This so-called quantum advantage stems from the quantum > > correlations present in quantum circuits that cannot be reproduced in > > analogous classical circuits." > > > > http://science.sciencemag.org/content/362/6412/308 > > > > Cheers, > > Telmo. > > > > -- You received this message because you are subscribed to the Google Groups "Everything List" group. To unsubscribe from this group and stop receiving emails from it, send an email to everything-list+unsubscr...@googlegroups.com. To post to this group, send email to everything-list@googlegroups.com. Visit this group at https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
