3
$\begingroup$

What quantum technologies and/or techniques (if any) could be used to evaluate the value of large numbers in the fast growing hierarchy such as Tree(3) or SCG(13)?

$\endgroup$
  • 2
    $\begingroup$ Given how large these numbers are -- even the number of digits that they have is extremely large -- what do you mean by 'approximate'? $\endgroup$ – Niel de Beaudrap Jul 6 '18 at 9:58
  • $\begingroup$ I've changed to evaluate (& am reminded of the quote "that depends on what the meaning of the word 'is' is"). What I'm after is a quantum approach (shor, grover, etc.) since classical approaches seem to fall short. Or an explanation as to why even quantum computation isn't sufficient for calculation. $\endgroup$ – meowzz Jul 6 '18 at 15:14
4
+50
$\begingroup$

The numbers you are describing are very very large. To the point, it appears that they are numbers whose representation in decimal (or binary) are large enough that it there is little to no prospect of there being enough matter in the entire universe to store those numbers, in a place-value representation such as those. This being the case, no technology — quantum or otherwise — will be able to produce a representation (or anything which can be described as a conventional 'estimate') of those numbers.

Furthermore, it appears that these functions are faster growing than any provably total function (e.g., faster than any function which we know to be computable even in exponential time) relative to some more-or-less sensible model of set theory. If you are interested in things which you can compute in a reasonable time-bound with quantum computers — e.g. in polynomial time, which can be simulated in at worst exponential time on a conventional computer — it follows that on mathematical grounds as well as physical grounds, you should expect these functions not to be practically computable even on an idealised quantum computer.

$\endgroup$
  • $\begingroup$ I suppose what I was hoping is that there would be a non-classical representation (especially in the case of Tree(3) & SCG(13)). Would this fall in the realm of np-complete? $\endgroup$ – meowzz Jul 6 '18 at 15:32
  • 1
    $\begingroup$ To start with, what would one do with a non-classical representation? What would it mean to 'represent' the number if we could not somehow access all of the digits? No matter what application you have in mind, there has to be something you want to use the information for, and some way of acting on the state to get that information out. In this case, you're asking about numbers which are in effect uncomputable: and as quantum computers can be simulated (if only very inefficiently) by classical computers, anything uncomputable for classical computers is also uncomputable for quantum computers. $\endgroup$ – Niel de Beaudrap Jul 6 '18 at 16:11
  • 1
    $\begingroup$ Now we're back to approximations: to produce some of the digits of pi, is to be able to approximate it to some precision, and in a specific and well-understood sense. If you wanted some of the digits of Tree(3), say, which digits would those be, and why? – Bear in mind also that any quantum algorithm to do this would also give a (much slower, admittedly) classical algorithm to do so: given that we seem to have only the very loosest of lower bounds for these numbers, it would be surprising if we could somehow produce estimates for it beyond the best mathematical theories we currently have. $\endgroup$ – Niel de Beaudrap Jul 6 '18 at 16:31
  • 1
    $\begingroup$ The simplest way to fast-forward quantum evolution is to increase the strength of the Hamiltonian by a corresponding multiplicative factor. That costs at least the same amount in energy. This brings us back to the question of whether the universe even has enough energy (or matter) to allow an explicit representation of the answer. $\endgroup$ – Niel de Beaudrap Jul 13 '18 at 9:28
  • 1
    $\begingroup$ As for the non-classical representation: I'm not sure what intuition I'm meant to take away from that video, but bear in mind that it only (!) takes an exponential amount of classical information to represent a quantum state, so it isn't clear that the space-savings from a "quantum representation" would be enough to allow us to store the state with the resources available on Earth. Nor to mention that a representation is only as good as what we can do with it: how would you want to use a 'quantum representation' of these large numbers? $\endgroup$ – Niel de Beaudrap Jul 13 '18 at 9:32

Your Answer

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

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