According to the reference Time/Space Trade-Offs for Reversible Computation by Charles H. Bennett given by Peter Shor in https://cstheory.stackexchange.com/questions/18938/is-there-any-task-where-classical-computers-outperform-quantum-computers,

Using a pebbling argument, this paper shows that, for any $\epsilon > 0$, ordinary multitape Turing machines using time $T$ and space $S$ can be simulated by reversible ones using time $O(T^{1+\epsilon})$ and space $O(S \log T)$ or in linear time and space $O(ST^{\epsilon})$.

Assume one can set $\epsilon$ as some number very close to $1$, so assume approximately $O(T)$ time and $O(S\log T)$ space are required with constant multiples not much larger than those of classical algorithm.

According to Quantum computers may have higher 'speed limits' than thought, QC may not suffer from the heat issue that the conventional architecture now suffers when the clock rate is risen, not to mention that there will be ultimately an upper bound for the clock rate of QC, but we don't know how high that will be. Anyway, assume QC will have much higher clock rate, say the order of peta Hz. With this, we want to build a faster quantum supercomputer that can deal with classical algorithms without faster quantum counterpart known (e.g. simulation of classical many-particle dynamics). Are there any known architectural reason that prevents this beside obvious things such as parallelizability of QC?

If you can't answer or don't want to answer my questions but know the relevant papers or books, please list them, as I couldn't find any.

  • $\begingroup$ "so assume ... with constant multiples not much larger than those of classical algorithm" - Well, you can't assume that. That doesn't follow from the statement that you quoted. Big-O notation explicitly avoids saying anything about how large the constant factors are. I realize this doesn't answer your question. Ultimately, right now we don't know whether quantum computing will be effective in practice, and I'm not sure we know what the limiting factors will be, so I'm not sure the question is answerable given our current knowledge. We'll see if someone here can answer. $\endgroup$ – D.W. Jul 6 '17 at 18:41
  • $\begingroup$ In the quoted post, Shor said "a quantum computer can perform any reversible classical computation, and if you keep the input around, any classical computation can be made reversible at a cost of multiplying the number of steps by a small constant factor." So, I believe it follows from this comment. $\endgroup$ – Math.StackExchange Jul 6 '17 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.