10

As a part of a discussion with my 'classical' friend, he insisted that making a a state machine for calculating the outcome of quantum computer is possible; so, simply calculate the outcomes of (known) algorithms on supercomputers and store their results in a Look-up table. (Something like storing the truth table).

So, why do people work on quantum simulators (say, capable up to 40 qubits); which calculate the result every time?! Simply (hypothetically) use the supercomputers of the world (say capable up to 60 qubits); calculate the result for $2^{60}$ input cases, store their result and use it as reference? How can I convince him it's not possible?

Note: this is for known quantum algorithms and their known circuit implementations.

Sanchayan Dutta
  • 17,945
  • 8
  • 50
  • 112
mando
  • 355
  • 3
  • 11

2 Answers2

14

Suppose that you have a quantum algorithm with $2^{60}$ possible inputs. Suppose also that it would take 1 nanosecond to run this on a supercomputer (which is unrealistically optimistic!). The total time required to run through all possible inputs would be 36.5 years.

Clearly it would be much better to just run the instance that you care about, and get the answer in an instant, rather than waiting half a lifetime to pick it from a list. This gets ever more true as we raise the runtime from the unrealistic 1 nanosecond.

why do people work on quantum simulators (say, capable up to 40 qubits); which calculate the result every time?!

Even if you wanted to create a lookup table, you'd still need a simulator like this to create it.

James Wootton
  • 11,700
  • 1
  • 35
  • 74
3

For a specific quantum algorithm that uses 40 qubits, your friend makes a good point. One can just calculate the truth table (one might find this hard, but assume that one can) and use it as reference. Of course this starts to get ridiculous as you increase the number of qubits, not just because of the number of inputs but because computing the outcome of a quantum algorithm could be exponentially harder classically for all we know.

However, being able to simulate a quantum computer (or having an actual quantum computer) is far more useful. By changing what quantum operations one does, one gets different algorithms. The number of functions that one can define on 40 bits of inputs is 2^2^40. Having a single database that gives you instant access to the results of any quantum algorithm is just absurdly infeasible. We want to be able to switch algorithms easily too, and classically we'd want simulators for that.

SuhailSherif
  • 131
  • 1