Alon Amit on Quora · 2023-06-25

Can a quantum computer calculate the factorial? This factorial is (( (((3!)!)!)!)!)! .

No. I would encourage you to ignore most of the nonsensical answers given here.

First of all, by “calculating” you probably mean producing the sequence of decimal digits of the indicated number. For example, calculating (3!)! means producing the number 720, and calculating ((3!)!)! means producing the 1747 digits of 720!, like so:

Honestly, this isn’t a particularly useful sense of “calculating”. The notation 720! uniquely specifies that number just as well as those 1747 digits, and in fact in many ways it’s substantially superior to those digits. But, whatever. If someone really needs those digits, here they are.

The next factorial, however, already requires more decimal digits than can be stored in the visible universe, and that’s putting it very mildly. it’s a number with more than 10^{1700} digits, which you may contrast with the commonly cited figure of 10^{80} atoms in the visible universe. You’ll need more than 10^{1620} universes to store those digits at a density of one digit per atom.

So say you have a quantum computer, or a schmantum computer, or whatever, and you want it to “calculate” (720!)!. What, exactly, do you expect will happen? The voodoo machine calculates that number and… what? Sends you an email with a PDF attachment? prints it really-really small?

You’re actually asking for an even larger number, one with like 10^{10^{10^{1700}}} digits. But it really doesn’t matter at this point. The task of “calculating” even just (720!)! is meaningless if you interpret it as producing the decimal digits. At the same time, the very expression you’ve used is an excellent notation for that number. You can do many, may things with this notation (like, for example, compute its approximate order or magnitude, or determine various arithmetic properties) which you couldn’t possibly do with the useless sequence of digits. So what are you “calculating” here, and why?


The other thing here is that quantum computers are neither known nor expected to offer any advantage in computing the decimal digits of factorials or whatnot. The common misconception, that they offer “infinite parallel computation” or some such gobbledygook, is just a misconception. So whatever computational task you are looking to solve with those factorials, there’s no reason to think that quantum computers would be able to offer even a little bit of help.

Originally posted on Quora: https://qr.ae/pyMBBU