The asymptotic time complexity of Grover's algorithm is the square root of the time of a brute force algorithm. However, according to Perlner and Liu, the thermodynamic behavior (theoretical minimum on energy consumption) is asymptotically the same as brute force.

Is there an analogous limit of Shor's algorithm? If so, this could potentially affect some cryptographic protocols.


1 Answer 1


I have been doing some work on understanding the thermodynamics of quantum algorithms for my undergraduate thesis.

Where is the Heat coming from?

The first thing you want to think about is, where is the thermodynamics going to come into play? I am choosing to focus on entanglement. Firstly because it's a natural place to build off of from a Landauer's principle point of view and secondly because entanglement is at the heart of so many quantum algorithms.

A relationship between entanglement and thermodynamics was explored by Marcus Huber, Marti Perarnau-Llobet and others in this paper. Here, you will find two major results, the first a constraint on how much entanglement you can produce given some heat and the second how much thermodynamic work need one do to produce some entanglement.

How do you measure the entanglement of a Quantum Algorithm?

With this you'd think we're off to the races and we can quickly use their work to analyse your case with Shor but here is the rub.

It is very difficult to determine the amount of entanglement in an algorithm (in fact here's a question I asked about it a year ago) and this is where the majority of the work I'm currently doing lies. Looking for ways around this.

You can also take an algorithm independent approach to examining the thermodynamics like some lovely people from Google did here by looking at Quantum Channels in a general sense.

Whilst I know that wasn't a direct answer to your question, I hope it was still informative.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.