4
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ As far as I know, it is generally possible to effectively simulate quantum processes (based on linear algebra) only on a quantum computer (of course, when it has an appropriate number of qubits and an acceptable level of noise immunity is achieved). Or a question about something else? $\endgroup$
    – Psanfi
    Commented Aug 16, 2020 at 7:00

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I see. Let me know if the following is correct. First off, to take advantage of the $2^n$ Hilbert space you need to be able to entangle all the qubits. In a fully connected quantum processor this would require $O(n^2)$ interconnects but this is still polynomial. The idea then is that, because of quantum entanglement, you get control over $2^n$ complex numbers even only having access to a polynomial number of "physical objects". The classical case, lacking entanglement, would always require $2^n$ "physical things" to encode the complex amplitudes? $\endgroup$
    – Jagerber48
    Commented Aug 16, 2020 at 18:41
  • $\begingroup$ Entanglement somehow allows for storage of information "between" the physical things in a way that gives more information storage and processing capabilities per physical thing.. $\endgroup$
    – Jagerber48
    Commented Aug 16, 2020 at 18:42
  • 1
    $\begingroup$ Regarding your last paragraph, we can efficiently simulate any Clifford circuit precisely because of such clever insights (representing a $n$-qubit state using $n$ stabilizers). However Clifford circuits are not complete. It does have repercussions for real quantum computing however, since we can implement the Clifford gates in a fault-tolerant way. And a Clifford circuit is complete if we give it access to some 'magic states': quantum states with specific values. See "Universal quantum computation with ideal Clifford gates and noisy ancillas." by Sergey Bravyi and Alexei Kitaev. $\endgroup$
    – orlp
    Commented Aug 17, 2020 at 1:58
  • $\begingroup$ @Jagerber48 Actually, I don't know whether $O(n^2)$ interconnects are always enough to construct the desired quantum state. In some cases (e.g. Quantum Fourier Transform) it seems to be enough, but there might be cases when it's not enough. I think it's worth asking in a separate thread! $\endgroup$
    – Attila Kun
    Commented Aug 20, 2020 at 11:45
  • 1
    $\begingroup$ @Jagerber48 And remember, it's not true that the classical case always requires $2^n$ space to encode complex amplitudes. If the amplitudes follow some well defined pattern, you might be able to significantly save on the space. For example, consider the uniform superposition state $\frac{1}{\sqrt{2^n}} \sum_{x} |x \rangle$. You can achieve this by applying $n$ Hadamard gates (one for each qubit). But classically, you could just store a single amplitude (since all are the same) and be done with it! So in this extreme example, the classical representation is more parsimonious in some sense. $\endgroup$
    – Attila Kun
    Commented Aug 20, 2020 at 12:21
3
$\begingroup$

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.

Improve this answer
$\endgroup$

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.