> On 21 Oct 2018, at 15:44, Telmo Menezes <[email protected]> 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.”
I guess they mean: … "This so-called quantum advantage stems from the quantum correlations present in quantum circuits that cannot be reproduced [In real time] in analogous classical circuits.” In real time, or in polynomial time, or something. If not that would violate Church’s thesis. It would be interesting to see if this is as much convincing that Deutsch original problem, to corroborate or not Deutsch argument in favour of Many-worlds. Will take a look when I have more time, very plausibly. Logarithmic grow is not impressive in that regard. Bruno > > 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. -- 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.
