There's a lot of mystifying jargon in the field of quantum computation, so I would like to pose a question from elementary physics to maybe help clarify things. Is it not true that the speed of a real-world reversible computer scales linearly with applied force and entropy? The Heisenberg energy-time bound shows that energy release per time step is greater than Planck's constant over the step time. Also, the bound on total entropy over a complete computation is O(Boltzmann's constant) to avoid decoherence. By Boltzmann law, if the entropy release per step is much greater than Boltzmann's constant, then the quantum computer decoheres, and noise will be read out. So the runtime of a general quantum computer seems to be lower bounded by $(h*S^2)/(k*T)$, where $S$ is the number of steps, $h$ is Planck’s constant, $k$ is Boltzmann’s constant and $T$ is the ambient temperature. The runtime bounds on Grover’s and Shor’s algorithms don’t look too impressive under this basic analysis. It seems that MT and ML bounds dramatically overestimate the speed of quantum evolution. What is a straightforward answer to this objection?

Update: I additionally found this article by John D. Norton. Abstract: "The thermodynamics of computation assumes that computational processes at the molecular level can be brought arbitrarily close to thermodynamic reversibility and that thermodynamic entropy creation is unavoidable only in data erasure or the merging of computational paths, in accord with Landauer’s principle. The no-go result shows that fluctuations preclude completion of thermodynamically reversible processes. Completion can be achieved only by irreversible processes that create thermodynamic entropy in excess of the Landauer limit."

  • $\begingroup$ I'm not enough of a physicist to give you a definitive answer, but are you sure your premise that "the speed of a real-world reversible computer scales linearly with applied force and entropy" is correct? If you have fully reversible computing, you don't need generate any entropy. That's why classical reversible computing would be nice, there is no heat you necessarily generate that you have to worry about dissipating (and then you just have to worry about non-idealities). $\endgroup$
    – Chris E
    Sep 29, 2022 at 2:20
  • $\begingroup$ But the more reversible the machine, the slower the computation. Correct? $\endgroup$ Sep 29, 2022 at 2:38
  • $\begingroup$ I believe it's a binary property classically. If you lose no information via reversible operations, then you've lost no information, regardless of how quickly you've done your operations. I'm not 100% sure this holds for the quantum case, because of the time-energy uncertainty bound. $\endgroup$
    – Chris E
    Sep 29, 2022 at 3:59
  • $\begingroup$ But don't you need to add energy to each step to increase the speed of computation? The cooler the computer, the slower the speed. This seems to be a very general result. $\endgroup$ Sep 29, 2022 at 6:20
  • 1
    $\begingroup$ @MDCory . If I plugged in the correct values for $h$ and $k$ and assume $T$ at room temperature your formula gives me a lower bound for a single step of 1.64 E-4 nano seconds. What is there not so impressive ? $\endgroup$
    – Kurt G.
    Sep 29, 2022 at 12:33


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.