Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Computer Engineering
Computation In Quantum Space-Time Could Lead To A Super-Polynomial Speedup, Vladik Kreinovich, Michael Zakharevich
Computation In Quantum Space-Time Could Lead To A Super-Polynomial Speedup, Vladik Kreinovich, Michael Zakharevich
Departmental Technical Reports (CS)
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 …