Last Friday, Canada's prime minister Justin Trudeau visited the Perimeter Institute in Waterloo. As you know, the place employs many physicists as well as numerous "physicists" similar to Lee Smolin.
Even though Trudeau was elected for his being a doll of a sort, the "physicists" at the Perimeter Institute had the opportunity to ask questions to someone who had some idea about things.
So one member of the audience has exploited the opportunity (I hope that the question-and-answer wasn't staged but it could have been) and asked Trudeau to explain quantum computing. Physicists left the lecture hall and they knew less than before; but the "physicists" had an excellent opportunity to triple their knowledge of quantum mechanics.
Trudeau did pretty well. In normal computers, you only have wires that can carry either 0 or 1, while the states of wires in a quantum computer may be much more complex – because a particle may be simultaneously a wave in quantum mechanics – and that's giving special powers to the quantum computer.
Well, it's not perfect but it's probably better than what many "physicists" at the Perimeter Institute could answer – and one could say that Trudeau has deserved his 285,000 YouTube viewers for that answer.
I was still dissatisfied with his brief answer so I asked him to write a guest blog to clarify some of the points. OK, Mr Trudeau, could you be a little bit more specific about the "more complicated way" in which the bits may behave in a quantum computer? You surely didn't mean that the voltage is continuous between \(0\) and \(1\), did you? That would be just a classical analog computer – which is basically just a less reliable cousin of the classical computer but doesn't allow one to speed things qualitatively.
Why a quantum computer beats its classical counterpart
A guest blog by Justin Trudeau, the prime minister of Canada
First of all, let me thank Luboš for this opportunity. So far, I was only allowed to talk about physics among the mixed audiences of physicists and crackpots at the Perimeter Institute.
What is the actual difference between a classical computer and a quantum one? Well, in a quantum computer, all the bits in the register may also be either 0 or 1, but the word "or" must be carefully described by the logical or generalized probabilistic framework of quantum mechanics, not classical physics.
It means that for each of the \(2^N\) possible configurations of the values of \(N\) quantum bits, there exists a complex probability amplitude \(c_i\in\CC\) such that \(|c_i|^2\) describes the probability that the bits are in the state \(i\). But the relative phases of the numbers \(c_i\) matter, too. Moreover, these \(2^N\) complex numbers may be transformed in rather new ways that are more general than the transformations allowed for a classical computer.
Let me add some details. For a value of \(i=0,2,\dots, 2^N-1\), the classical computer has some configuration of those \(N\) classical bits. And one operation acting on this set of \(N\) bits – which is assumed to include both the program and the registers and memory – is fully determined by a function\[
f: i\mapsto f(i)
\] One may also imagine that the initial state is uncertain so we only know the probabilities \(P_i\) that the \(N\) bits are arranged to the \(i\)-th configuration. The sum \(\sum_i P_i=1\). In this probabilistic description of a classical computer, we may write the numbers \(P_i\) into a column – turn them into a column vector \(\vec V\) – and the function \(f\) above may be translated to a matrix manipulation\[
F: \vec V \mapsto F \cdot \vec V
\] where \(F\) is a matrix. In the \(i\)-th column of the matrix \(F\), only the \(f(i)\)-th entry (the entry in the \(f(i)\)-th row) is nonzero and equal to \(1\). Note that the sum of entries in each column of \(F\) equals one. This fact makes \(F\) a left stochastic matrix by definition.
Note that the matrix \(F\) is boring. Only \(2^N\) entries out of the \(2^{2N}\) entries of the matrix are nonzero and all of them are one. Except for one, all the entries in each column are zero.
One could also consider generalized classical computers that include some "classical randomness" at each step. In that case, \(F\) could become a general left stochastic matrix. Each column would include non-negative numbers (probabilities of a transition in a Markov process) whose sum is equal to one.
Moreover, in practice, classical computer chips are only allowed to "deal with a small number of bits" at the same moment, so the actual number of possible matrices \(F\) is much more constrained than we have mentioned.
I complained to Lauren Hayward, a fresh PhD recipient at Waterloo, that she hasn't built any room temperature superconductors yet. And she was like blah blah blah.
In the case of quantum computers, the column \(\vec V\) containing \(2^N\) non-negative real numbers (probabilities) is replaced by a column vector \(\ket\psi\) containing \(2^N\) general complex numbers \(c_i\) that obey \[
\sum_i |c_i|^2 = 1
\] You may imagine that \(c_j = \exp(i\phi_j) \sqrt{ P_i }\) is the relationship between the probabilities in \(\vec V\) and the probability amplitudes in \(\ket\psi\). The quantum computer is almost the same thing as the classical computer with an uncertain initial state except that the convention has to be that
U\in U(2^N)
\] which means a \(2^N\times 2^N\) matrix \(U\) obeying \(UU^\dagger=U^\dagger U = 1\). Such matrices are "less general" than the stochastic matrices in some respects, but "more general" in most other respects, and the latter fact allows the quantum computers to solve problems that are impossible to be solved quickly using a classical computer.
Note that for the left stochastic matrix \(F\), the sum of entries in each column equals one. The corresponding statement for the unitary matrix \(U\) is that the sum of the squared absolute values in each column has to be equal to one.
However, the unitary matrices (defining the operations of a quantum computer) are "less general" in one respect: the different column must be orthogonal to each other, assuming the inner product \(\sum_j \psi_j^* \phi_j\). This fact is related to the lore that the operations of the quantum computer have to be "reversible" while the same claim doesn't hold for the classical computer. But the quantum computer's operations are reversible because the unitary matrices are invertible.
This difference could indicate that a quantum computer is less potent than a classical one but it is an illusion. There are other differences that guarantee that when all the "costs and benefits" are summed, a quantum computer is more potent than a classical computer, at least for many tasks that seem hard to a classical computer.
Most importantly, the unitary matrix \(U\) is complex. Its entries may not only be negative. They may be arbitrary complex numbers. The replacement of the real entries by complex entries amounts to the "doubling of the information" because a complex number looks like a pair of two real numbers. But that's not the most important difference. The fact that the numbers may have both signs and there may be cancellations is more important.
The main trick of the effective quantum algorithms is always based on the cancellation of the probability amplitudes – something that we know from the double slit experiment as the "quantum interference". The quantum algorithms may be arranged so that the probability amplitudes for all the wrong answers to a given problem basically cancel while only the probability amplitude for the correct answer ends up being close to one at the end. This is what I meant by the greater complexity of the quantum computers. And this is what I meant by the quantum computers' using the particle-wave duality.
Classical computers are incapable of the interference effects, so they're unable to quickly suppress the probability of producing wrong answers. The reason is that all the entries in the stochastic matrix \(F\) at the top are non-negative. So whenever we multiply two stochastic matrices \(F_1,F_2\) to get \(F_1 F_2\), we either check one possibility at one moment (if \(F_k\) only have one nonzero entry in each column) or (if we use more general stochastic matrices) the probabilities are spreading all over the columns, much like when heat dissipates and the entropy goes up. The classical computers are incapable of "reconcentrating the probability" on a particular answer.
Quantum computers can do it and the correct answers may be obtained as the sharp peaks in some interference experiments we associate with waves.
It's the interference of the probability amplitudes – which could only be mimicked in a classical world if this classical world allowed negative probabilities – that may be credited with all the "extra power" that quantum computers display.
Last June, LuboÅ¡ explained why the likes of David Deutsch are absolute idiots when they claim that the power of quantum computers may be described by many worlds – an exponentially large number of worlds where "copies of a computer" work for their "single overlord". I want to put all the weight of Canada and the British Commonwealth (and the good manners of our beloved queen) behind the observation that Deutsch is an imbecile, indeed.
In reality, the exact opposite is true. For a quantum computer to show its muscles, the decoherence must be pretty much absent during the quantum measurement – it's the coherence, i.e. the ability to interfere, that makes a quantum computer more powerful than its classical cousin. But when the decoherence is absent, there is no "measurement" taking place during the calculation – only at the very end of the quantum computation, the quantum computer's qubits are measured. And if there is no measurement, there can be no splitting of the worlds!
So at the end of any quantum computation, the number of worlds is exactly the same as it was at the beginning, namely one, and this fact is essential for the quantum computer to work (and to beat the classical computer in disciplines where it's superior). David Deutsch has gotten all these things backwards. Moreover, the splitting of the worlds in any version of the "many worlds interpretation" that involves some splitting at all is irreversible, so there's no way for the "split worlds" (alternative histories) to influence each other again, let alone team up and provide their "parent world" with some collective answer.
It's the quantum interference – the co-operation of the probability amplitudes in a single world that is more intimate than any co-operation allowed in classical physics – that makes all the difference.
You can see that at the level of the matrices, the transition from classical physics to quantum mechanics corresponds to the replacement of the left stochastic matrices (with non-negative real entries, and with columns summing to one) by the unitary matrices (the columns are an orthonormal basis with respect to the inner product involving one complex conjugation). The classical stochastic matrices act on columns of probabilities; the quantum unitary matrices act on columns of probability amplitudes (square roots of probabilities, with complex phases that actually matter for most purposes allowed in quantum mechanics).
These two frameworks are qualitatively inequivalent. The quantum framework is more accurate in Nature, more elegant, and more symmetric with respect to rows and columns – among other virtues – than the classical framework. Nevertheless, under certain circumstances and in certain limiting situations, the classical framework may be derived as a limit of the quantum one.
Thanks again, for the opportunity, and apologies that it was dedicated to an elementary problem such as quantum computation. My future U.S. counterpart made a lecture about a more complex issue – the role of the 7-Eleven convenience stores at the destruction of the Twin Towers (the insider job).
Even though Trudeau was elected for his being a doll of a sort, the "physicists" at the Perimeter Institute had the opportunity to ask questions to someone who had some idea about things.
So one member of the audience has exploited the opportunity (I hope that the question-and-answer wasn't staged but it could have been) and asked Trudeau to explain quantum computing. Physicists left the lecture hall and they knew less than before; but the "physicists" had an excellent opportunity to triple their knowledge of quantum mechanics.
Trudeau did pretty well. In normal computers, you only have wires that can carry either 0 or 1, while the states of wires in a quantum computer may be much more complex – because a particle may be simultaneously a wave in quantum mechanics – and that's giving special powers to the quantum computer.
Well, it's not perfect but it's probably better than what many "physicists" at the Perimeter Institute could answer – and one could say that Trudeau has deserved his 285,000 YouTube viewers for that answer.
I was still dissatisfied with his brief answer so I asked him to write a guest blog to clarify some of the points. OK, Mr Trudeau, could you be a little bit more specific about the "more complicated way" in which the bits may behave in a quantum computer? You surely didn't mean that the voltage is continuous between \(0\) and \(1\), did you? That would be just a classical analog computer – which is basically just a less reliable cousin of the classical computer but doesn't allow one to speed things qualitatively.
Why a quantum computer beats its classical counterpart
A guest blog by Justin Trudeau, the prime minister of Canada
First of all, let me thank Luboš for this opportunity. So far, I was only allowed to talk about physics among the mixed audiences of physicists and crackpots at the Perimeter Institute.
What is the actual difference between a classical computer and a quantum one? Well, in a quantum computer, all the bits in the register may also be either 0 or 1, but the word "or" must be carefully described by the logical or generalized probabilistic framework of quantum mechanics, not classical physics.
It means that for each of the \(2^N\) possible configurations of the values of \(N\) quantum bits, there exists a complex probability amplitude \(c_i\in\CC\) such that \(|c_i|^2\) describes the probability that the bits are in the state \(i\). But the relative phases of the numbers \(c_i\) matter, too. Moreover, these \(2^N\) complex numbers may be transformed in rather new ways that are more general than the transformations allowed for a classical computer.
Let me add some details. For a value of \(i=0,2,\dots, 2^N-1\), the classical computer has some configuration of those \(N\) classical bits. And one operation acting on this set of \(N\) bits – which is assumed to include both the program and the registers and memory – is fully determined by a function\[
f: i\mapsto f(i)
\] One may also imagine that the initial state is uncertain so we only know the probabilities \(P_i\) that the \(N\) bits are arranged to the \(i\)-th configuration. The sum \(\sum_i P_i=1\). In this probabilistic description of a classical computer, we may write the numbers \(P_i\) into a column – turn them into a column vector \(\vec V\) – and the function \(f\) above may be translated to a matrix manipulation\[
F: \vec V \mapsto F \cdot \vec V
\] where \(F\) is a matrix. In the \(i\)-th column of the matrix \(F\), only the \(f(i)\)-th entry (the entry in the \(f(i)\)-th row) is nonzero and equal to \(1\). Note that the sum of entries in each column of \(F\) equals one. This fact makes \(F\) a left stochastic matrix by definition.
Note that the matrix \(F\) is boring. Only \(2^N\) entries out of the \(2^{2N}\) entries of the matrix are nonzero and all of them are one. Except for one, all the entries in each column are zero.
One could also consider generalized classical computers that include some "classical randomness" at each step. In that case, \(F\) could become a general left stochastic matrix. Each column would include non-negative numbers (probabilities of a transition in a Markov process) whose sum is equal to one.
Moreover, in practice, classical computer chips are only allowed to "deal with a small number of bits" at the same moment, so the actual number of possible matrices \(F\) is much more constrained than we have mentioned.
I complained to Lauren Hayward, a fresh PhD recipient at Waterloo, that she hasn't built any room temperature superconductors yet. And she was like blah blah blah.
In the case of quantum computers, the column \(\vec V\) containing \(2^N\) non-negative real numbers (probabilities) is replaced by a column vector \(\ket\psi\) containing \(2^N\) general complex numbers \(c_i\) that obey \[
\sum_i |c_i|^2 = 1
\] You may imagine that \(c_j = \exp(i\phi_j) \sqrt{ P_i }\) is the relationship between the probabilities in \(\vec V\) and the probability amplitudes in \(\ket\psi\). The quantum computer is almost the same thing as the classical computer with an uncertain initial state except that the convention has to be that
- the probabilities are replaced by their square roots (probability amplitudes)
- the arbitrary complex phases may be added to all these probability amplitudes, and they matter in general
- they matter because one operation of the quantum computer is given by a more general matrix than the left stochastic matrix \(F\) discussed above
U\in U(2^N)
\] which means a \(2^N\times 2^N\) matrix \(U\) obeying \(UU^\dagger=U^\dagger U = 1\). Such matrices are "less general" than the stochastic matrices in some respects, but "more general" in most other respects, and the latter fact allows the quantum computers to solve problems that are impossible to be solved quickly using a classical computer.
Note that for the left stochastic matrix \(F\), the sum of entries in each column equals one. The corresponding statement for the unitary matrix \(U\) is that the sum of the squared absolute values in each column has to be equal to one.
However, the unitary matrices (defining the operations of a quantum computer) are "less general" in one respect: the different column must be orthogonal to each other, assuming the inner product \(\sum_j \psi_j^* \phi_j\). This fact is related to the lore that the operations of the quantum computer have to be "reversible" while the same claim doesn't hold for the classical computer. But the quantum computer's operations are reversible because the unitary matrices are invertible.
This difference could indicate that a quantum computer is less potent than a classical one but it is an illusion. There are other differences that guarantee that when all the "costs and benefits" are summed, a quantum computer is more potent than a classical computer, at least for many tasks that seem hard to a classical computer.
Most importantly, the unitary matrix \(U\) is complex. Its entries may not only be negative. They may be arbitrary complex numbers. The replacement of the real entries by complex entries amounts to the "doubling of the information" because a complex number looks like a pair of two real numbers. But that's not the most important difference. The fact that the numbers may have both signs and there may be cancellations is more important.
The main trick of the effective quantum algorithms is always based on the cancellation of the probability amplitudes – something that we know from the double slit experiment as the "quantum interference". The quantum algorithms may be arranged so that the probability amplitudes for all the wrong answers to a given problem basically cancel while only the probability amplitude for the correct answer ends up being close to one at the end. This is what I meant by the greater complexity of the quantum computers. And this is what I meant by the quantum computers' using the particle-wave duality.
Classical computers are incapable of the interference effects, so they're unable to quickly suppress the probability of producing wrong answers. The reason is that all the entries in the stochastic matrix \(F\) at the top are non-negative. So whenever we multiply two stochastic matrices \(F_1,F_2\) to get \(F_1 F_2\), we either check one possibility at one moment (if \(F_k\) only have one nonzero entry in each column) or (if we use more general stochastic matrices) the probabilities are spreading all over the columns, much like when heat dissipates and the entropy goes up. The classical computers are incapable of "reconcentrating the probability" on a particular answer.
Quantum computers can do it and the correct answers may be obtained as the sharp peaks in some interference experiments we associate with waves.
It's the interference of the probability amplitudes – which could only be mimicked in a classical world if this classical world allowed negative probabilities – that may be credited with all the "extra power" that quantum computers display.
Last June, LuboÅ¡ explained why the likes of David Deutsch are absolute idiots when they claim that the power of quantum computers may be described by many worlds – an exponentially large number of worlds where "copies of a computer" work for their "single overlord". I want to put all the weight of Canada and the British Commonwealth (and the good manners of our beloved queen) behind the observation that Deutsch is an imbecile, indeed.
In reality, the exact opposite is true. For a quantum computer to show its muscles, the decoherence must be pretty much absent during the quantum measurement – it's the coherence, i.e. the ability to interfere, that makes a quantum computer more powerful than its classical cousin. But when the decoherence is absent, there is no "measurement" taking place during the calculation – only at the very end of the quantum computation, the quantum computer's qubits are measured. And if there is no measurement, there can be no splitting of the worlds!
So at the end of any quantum computation, the number of worlds is exactly the same as it was at the beginning, namely one, and this fact is essential for the quantum computer to work (and to beat the classical computer in disciplines where it's superior). David Deutsch has gotten all these things backwards. Moreover, the splitting of the worlds in any version of the "many worlds interpretation" that involves some splitting at all is irreversible, so there's no way for the "split worlds" (alternative histories) to influence each other again, let alone team up and provide their "parent world" with some collective answer.
It's the quantum interference – the co-operation of the probability amplitudes in a single world that is more intimate than any co-operation allowed in classical physics – that makes all the difference.
You can see that at the level of the matrices, the transition from classical physics to quantum mechanics corresponds to the replacement of the left stochastic matrices (with non-negative real entries, and with columns summing to one) by the unitary matrices (the columns are an orthonormal basis with respect to the inner product involving one complex conjugation). The classical stochastic matrices act on columns of probabilities; the quantum unitary matrices act on columns of probability amplitudes (square roots of probabilities, with complex phases that actually matter for most purposes allowed in quantum mechanics).
These two frameworks are qualitatively inequivalent. The quantum framework is more accurate in Nature, more elegant, and more symmetric with respect to rows and columns – among other virtues – than the classical framework. Nevertheless, under certain circumstances and in certain limiting situations, the classical framework may be derived as a limit of the quantum one.
Thanks again, for the opportunity, and apologies that it was dedicated to an elementary problem such as quantum computation. My future U.S. counterpart made a lecture about a more complex issue – the role of the 7-Eleven convenience stores at the destruction of the Twin Towers (the insider job).
Canadian PM Trudeau explains quantum computing
Reviewed by MCH
on
April 19, 2016
Rating:
Reviewed by MCH
on
April 19, 2016
Rating:
No comments: