Computation in quantum space-time could lead to a super-polynomial speedup
Michael Zakharevich, Владик Крейнович · Journal of Uncertain Systems · 2011
In theoretical computer science, researchers usually distinguish between feasible problems (that can be solved in polynomial time) and problems that require more computation time. A natural question is: can we use new physical processes, processes that have not been used in modern computers, to make computations drastically faster { e.g., to make intractable problems feasible? Such a possibility would occur if a physical process provides a super-polynomial (= faster than polynomial) speed-up. In this direction, the most active research is undertaken in quantum computing. It is well known that quantum processes can drastically speed up computations; however, there are no proven super-polynomial quantum speedups of the overall computation time. Parallelization is another potential source of speedup. In Euclidean space, parallelization only leads to a polynomial speedup. We show that in quantum space-time, parallelization could potentially lead to (provably) super-polynomial speedup of computations. c 2012 World Academic Press, UK. All rights reserved.