Timeline for To what extent is it true that quantum computation cannot be simulated on classical computers, and how can we prove it?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 11, 2016 at 20:40 | comment | added | Abhinav | Clarification- Scott's lecture shows that BQP $\subseteq$ PP, a stronger result than BQP $\subseteq$ PSPACE. | |
| Jul 11, 2016 at 20:33 | comment | added | Abhinav | For a paper that showed this, look at Theorem 8.4 of Bernstein-Vazirani's paper that introduced BQP. | |
| Jul 11, 2016 at 20:33 | comment | added | Abhinav | It is not necessary to store the state to simulate a quantum computation where there is a measurement at the end. All that is needed to be done to simulate the computation is to evaluate the amplitude corresponding to the accept state of the output, which can be done by keeping track of all (the exponentially many) possible paths from the input state to the accept state. For a reference, check out this lecture of Scott Aaronson's. | |
| Jul 10, 2016 at 17:35 | comment | added | zeldredge | @tparker it was an assigned problem in a course I took, but actually I may be wrong about that now that I think about it (because how can you store the state in polynomial space?). I will try to make this more precise soon. | |
| Jul 10, 2016 at 17:35 | comment | added | zeldredge | @sumelic you are correct | |
| Jul 10, 2016 at 17:33 | history | edited | zeldredge | CC BY-SA 3.0 |
deleted 21 characters in body
|
| Jul 9, 2016 at 21:14 | comment | added | tparker | Do you have a reference for using path-integrals to show that quantum computing is possible in polynomial space? | |
| Jun 29, 2016 at 19:53 | history | edited | zeldredge | CC BY-SA 3.0 |
clarified that factoring might be easy
|
| Jun 29, 2016 at 18:18 | comment | added | zeldredge | @EmilioPisanty yes precisely! This is what I meant by saying "appear to be exponential." I'll edit later to reflect I think | |
| Jun 29, 2016 at 18:14 | comment | added | Emilio Pisanty | Or, to be more explicit, problems like factoring can be solved efficiently by quantum computers and not by any known classical algorithms - but this might yet change! For all we know, factoring is efficiently solvable (i.e. in P). | |
| Jun 29, 2016 at 17:40 | history | answered | zeldredge | CC BY-SA 3.0 |