Thermodynamic Speed Limit to Quantum Computing

Question

There's a lot of mystifying jargon in the field of quantum computation, so I would like to examine some elementary physics to maybe help clarify the assumptions being made.

Is it not true that the speed of a real-world reversible computer scales linearly with applied force and entropy? To prove this, I will use $N$ as the number of steps (physical operations), $h$ as Planck’s constant, $k$ as Boltzmann’s constant, $S$ as entropy and $T$ as ambient temperature. By the Heisenberg time-energy uncertainty principle, $δE > h/δt$. With $δE$ released as heat, you get $T\cdot δS = δΕ > h/(T \cdot δt)$. Total entropy obviously can't exceed $O(k)$. Considering the Planck-Boltzmann formula, $δS$ much greater than $k$ decoheres into $O(e^{δS/k})$ independent microstates, while you can only read out $O(e^{-δS/k})$ of them. This means that for $N$ steps, the averaged entropy per step must be of $O(k/N)$. Putting these results together, you get a runtime of $Ω(h \cdot N^2/k \cdot T)$. Grover’s and Shor’s algorithms don’t look too impressive under this basic analysis, especially after considering memory requirements. It seems that MT and ML bounds dramatically overestimate the speed of quantum evolution.

An article by John D. Norton disputes the legitimacy of Landauer’s principle:

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.

It seems that Landauer and Bennett ignore quantum fluctuations, which are a major impediment to their arguments. That's besides the fact that QFT is a relativistic, nonlinear and infinite-dimensional theory of interacting fields (not particles), where measurement imposes discreteness by projecting the state into specific eigenstates. Uncertainty doesn't imply any form of analog error correction.

My Question: What is a straightforward answer to the fact that a QC needing $N$ operations takes at least $O(N^2)$ time to complete?

Update 1: I'm obviously referring to fundamental physical operations and not logical gates. Logical gates are an abstraction from the physics and can be very complicated to implement. For instance, the inefficiency of creating high-fidelity magic states poses a major challenge. A recent paper estimated that the overhead of distilling non-Clifford Toffoli gates is massive (~130,000 physical qubits) and leads to huge slowdowns (~170μs): "...quadratic speedups will not enable quantum advantage on early generations of such fault-tolerant devices unless there is a significant improvement in how we would realize quantum error-correction...this conclusion persists even if we were to increase the rate of logical gates in the surface code by more than an order of magnitude..."

Update 2: The stated asymptotic runtime complexities of Grover's and Shor's algorithms are based on the number of calls to the underlying circuits/operations, not the number of fundamental physical gates. If a reduction of gates made any difference to the argument, then the runtime bounds would be different in the literature. My argument is more general than these engineering problems.

Update 3: The threshold theorem assumes that the underlying physical error rate is a constant, independent of the size of the computation. However, the thermodynamic analysis shows that the minimum possible physical error rate is dependent on the size of the computation, due to the scaling of entropy generation.

Answer 1

I think there's some difficulty in communication and a lack of common language between physics and computer science, that make the question hard to answer. But I'll try to give some the computer science perspectives.

Initially I emphatically reject the assertion that there's a massive refutation of most quantum computation claims, because as has been mentioned many times quantum computers provide speedups by reducing the number of needed operations and not by reducing the amount of time required to perform any particular operation. Indeed, most gate operations would likely take significantly longer on a quantum computer than on a classical computer. But, there's just so many fewer operations needed on the quantum computer. I will quote Shor himself:

My favorite analogy is with transportation. Think of a quantum computer as a boat and a classical computer as a car. Suppose you want to go from New London, CT to Orient, NY. The ferry will take 80 minutes. Google Maps says the distance is 210 miles. So clearly, the ferry is averaging 157.5 miles per hour, right? No, it's taking a different path that is shorter (but that only boats can take). Similarly, Shor's algorithm is taking a different path that is shorter (but that only quantum computers can take).

Two other points for consideration:

1. In the comments the statement is provided that "the more reversible the machine, the slower the computation. Correct?" But, since the 70's/early 80's, we've known how to take any classical circuit that is irreversible, and convert the circuit to one that's reversible, at the cost of doubling the number of gates or operations. This has been referred to as Bennett's trick of uncomputation. (If the circuit uses recursion then there are some other issues, but in general this doubling is applicable). So yes, a reversible circuit will use more gates than an irreversible one, but only up to twice-as-many most of the time. If, as is claimed by Grover, a quantum computer can run in square-root-of-time, then the doubling of the circuit length to make it reversible is easily swamped out by the quadratic improvement in the number of calls to the circuit.

2. The appeal to the time-energy uncertainty principle is not misplaced! And indeed there is a theorem in quantum computing directly analogous to this principle - namely, the idea that most Hamiltonians admit no fast-forwarding. This means that for many Hamiltonians, the only way to get very accurate estimates of a Hamiltonian's energy is by actively running the simulation for longer and longer times. There are interesting exceptions to the no fast-forwarding theorem - with Shor's algorithm being the prototypical example.

ADDED

Much of your concerns were emphasized early on, especially after Shor's algorithm was introduced - but, the feeling of the community was that these were addressed with the proof of the Threshold Theorem which, although I'm not an expert on, notes that if an error rate per gate can be kept below a certain value then error correction wins in the long run. As indicated above quantum computing can win out in the long run by reducing the number of gates required. The error correction likewise only uses a linear(ish) number of additional qubits.

Your comment that you are "referring to fundamental physical operations and not gates" is inscrutable to me. Quantum gates are physical operations - e.g. microwave pulses on a coupler or lasers fired at ions.

Additionally I read the Google paper you linked to as throwing cold-water on being able to achieve a quantum computational advantage by running Grover's algorithm with the currently existing error correcting schemes. They did not show that Grover's algorithm scales as $O(N)$ as you seem to assert; rather, it emphasizes that the advantage of Grover's algorithm may be difficult to realize with existing hardware and error-correcting schemes. There is a legitimate criticism that much of theoretical computer science ignores constant overheads, but the assertion that "a QC needing $S$ operations takes at least $O(S^2)$ time to complete" is not established by your question or your linked papers.