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 [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
