4

A quantum algorithm begins with a register of qubits in an initial state, a unitary operator (the algorithm) manipulates the state of those qubits, and then the state of the qubits is read out (or at least some information about the state on a single run of the algorithm).

It seems to me that a quantum computer answers the question of the unitary acts on the quantum state. This is "just" a matter of linear algebra. It strikes me, then, that quantum computers can be seen as linear algebra calculators.

Why then do we need quantum mechanics? Can we not find a classical system which implements linear algebra operations and use this to implement the algorithms which have been designed for quantum computers? Of course classical digital computers will not suffice, these machines are based on binary processing of information rather than the manipulation of vectors in a high dimensional space.

Question: Are there any candidates for classical linear algebra solvers (classical analog computers) which could implement the "quantum computer" algorithms whiles enjoying a similar speedup over digital classical computers?

Question 2: Perhaps I'm over simplifying by reducing a quantum computer to being simply a linear algebra solver. Is this the case? What complexity am I glossing over?

glS
  • 27,510
  • 7
  • 37
  • 125
Jagerber48
  • 195
  • 7

2 Answers2

6

The complexity that you are glossing over is that in the general case you need to store $2^n$ complex amplitudes to even represent an $n$ qubit system classically. Therefore, for a quantum computer of let's say 1000 qubits you need to store $2^{1000}$ complex amplitudes. Even if you use one atom per amplitude to do this, you still run out of atoms in the observable universe.

As far as I know, the above is the general argument. However, there might still be ways to represent certain quantum algorithms in a classically tractable manner by utilising some clever insight to save on the representational needs of the algorithm, thereby going below the $2^n$ requirement. But this is likely to be problem-specific and unlikely to work in the general case.

Attila Kun
  • 579
  • 5
  • 10
3

As per the question's statement regarding digital vs. analog computation, there are other threads on this site that have inquired about similar proposals. See, e.g., here, and here. Among other things, classical analog systems cannot engage in entanglement; thus recasting a quantum computer as an analog computer will not lead to the same observed speed-up.

Nonetheless, further to @Attila Kun's answer there are specific problems in linear algebra/machine learning that have had fast quantum algorithms but have been recast as classical algorithms having similar speedups.

For example, the recommendation problem used by Netflix/Amazon/etc. has a fast algorithm on a quantum computer. This algorithm showed exponential improvement over the (then) best-known classical algorithm.

However, in attempting to prove that the quantum algorithm truly was superior, E. Tang showed that there was indeed a "classical system which implements linear algebra operations and use[s] this to implement the algorithms which have been designed for quantum computers".

Tang's work has kicked off a program of dequantization - i.e. of redesigning fast quantum algorithms in linear algebra/machine learning as fast classical algorithms. A Quanta Magazine article describes the problem and Tang's approach.

Which problems are amenable to this dequantization is an active area of research, as this thread discusses. This may depend on the rank of the matrices considered.

Mark Spinelli
  • 15,378
  • 3
  • 26
  • 83