Neven's Law
25 views
Skip to first unread message
John Clark
Jun 20, 2019, 7:19:47 AM6/20/19
to everyth...@googlegroups.com
In December 2018 researchers at Google solved a problem on their best quantum computer, but a low end laptop computer could solve it too. In January of this yearan improved quantum computer solved a more complicated version of the problem that took a high end desktop computer to equal. By February they had to use Google's huge server network of conventional computers to do what the Quantum Computer did.
If it turns out that Neven's law is anywhere close to being true then hold on to your buts because we're in for a bumpy ride.
Granted the problem chosen in the above was picked not because it was useful but because it best highlighted what a Quantum Computer could do; nevertheless a counterpart of Moore's law for conventional computers has been proposed called Neven's Law named after the head of Google’s Quantum Artificial Intelligence lab Hartmut Neven.
Neven's Law states that quantum computers are gaining computational power relative to conventional computers at a double exponential rate (2^(2)^2 , 2^(2)^3 , 2^(2)^4 , 2^(2)^5 ...)
John K Clark
Lawrence Crowell
Jun 20, 2019, 10:04:55 PM6/20/19
to Everything List
There is a bit of a major hurdle to leap over. That is decoherence. If you write a simple program on the QE it runs in less than 10^{-6} seconds and that is about all the time you have. The highly entangled quantum states become mixed state entangled with the environment states and the execution of the algorithm falls apart. Quantum error correction has its limits, which is related to the limitations of using Hamming distance. So for now quantum computers are in a bit of a niche market of sorts, and their practical use is largely with encryption. I do though suspect before long ordinary computers will have some qubit processor that will be executed in some algorithms.
LC
John Clark
Jun 21, 2019, 7:11:03 PM6/21/19
to everyth...@googlegroups.com
> There is a bit of a major hurdle to leap over. That is decoherence. If you write a simple program on the QE it runs in less than 10^{-6} seconds and that is about all the time you have.
Yes, decoherence has always been the big problem, that's why Microsoft wants to build a Topological Quantum Computer that uses braided non-Abelian Majorana sudo-particles called "anyons "; they are much less susceptible to decoherence than anything else for the same reason a random bump is unlikely to untie a knot. In the August 23 2017 issue of the journal Nature the Microsoft people report they have managed to braid anyons in a hashtag # arrangement of wires. These braids can encode a Qbit of quantum information and they can be manipulated.
There is also a short video that gives a outline of the above:
> The highly entangled quantum states become mixed state entangled with the environment states and the execution of the algorithm falls apart.Quantum error correction has its limits, which is related to the limitations of using Hamming distance.
The biggest difficulty comes from the No Cloning Theorem, it says you can't make an identical copy of an unknown quantum state, in other words you can't copy a Qbit. So quantum error correction algorithms are longer and more complex than for conventional error correction, and thus you have to worry more about errors produced when running the quantum error algorithm itself.
Nevertheless It has been proven you could theoretically make a arbitrary large quantum computer even if the underlining quantum gate had a error rate as high as 3%, although the amount of overhead needed for error correction would be so large it probably wouldn't be practical. But the overhead drops fast with increased gate reliability, if you can get the error rate down to 1% then it looks like a Quantum Computer of arbitrary size is practical as well as possible.
> for now quantum computers are in a bit of a niche market of sorts, and their practical use is largely with encryption.
Somebody will certainly use Shor's factoring algorithm to break RSA encryption once they get their hands on a Quantum Computer, but I think the killer application will be in efficient quantum simulation; imagine dreaming up a complex shape you want a protein to fold up into and the computer telling you what sequence of amino acids will fold up into exactly that shape. It would revolutionize medicine and chemistry not to mention give a big shot in the arm to Drexler style Nanotechnology.
> I do though suspect before long ordinary computers will have some qubit processor that will be executed in some algorithms.
Maybe but I doubt it. Nobody knows if a conventional computer could solve all nondeterministic polynomial time problems in polynomial time, we don't even know if a Quantum Computer can do that, but there has been a recent development that I find suggestive. Even if, to everybody's surprise, it turned out that P=NP and even if we had a algorithm that could solve NP problems on a conventional computer in polynomial time there would STILL be a class of problems a conventional computer couldn’t solve efficiently but a quantum computer could. Yes this class of problems is very exotic and nobody knowns if they have any fundamental interest in themselves or if they're interesting only because a conventional computer can’t solve them, but still...
John K Clark
Lawrence Crowell
Jun 21, 2019, 8:13:23 PM6/21/19
to Everything List
On Friday, June 21, 2019 at 6:11:03 PM UTC-5, John Clark wrote:
> There is a bit of a major hurdle to leap over. That is decoherence. If you write a simple program on the QE it runs in less than 10^{-6} seconds and that is about all the time you have.Yes, decoherence has always been the big problem, that's why Microsoft wants to build a Topological Quantum Computer that uses braided non-Abelian Majorana sudo-particles called "anyons "; they are much less susceptible to decoherence than anything else for the same reason a random bump is unlikely to untie a knot. In the August 23 2017 issue of the journal Nature the Microsoft people report they have managed to braid anyons in a hashtag # arrangement of wires. These braids can encode a Qbit of quantum information and they can be manipulated.There is also a short video that gives a outline of the above:
I have heard of this. I think they are using graphene sheets for this.
> The highly entangled quantum states become mixed state entangled with the environment states and the execution of the algorithm falls apart.Quantum error correction has its limits, which is related to the limitations of using Hamming distance.The biggest difficulty comes from the No Cloning Theorem, it says you can't make an identical copy of an unknown quantum state, in other words you can't copy a Qbit. So quantum error correction algorithms are longer and more complex than for conventional error correction, and thus you have to worry more about errors produced when running the quantum error algorithm itself.
The nocloning theorem means there is no unitary process that can duplicate a state. If you have a state ψ = aχ_1 + bχ_2 then the duplication ψ → ψψ is the state in the {χ_1, χ_2} basis representation.
χ_1 + bχ_2 → (aχ_1 + bχ_2)(aχ_1 + bχ_2) = a^2χ_1χ_1 + 2abχ_1χ_2 + b^2χ_1χ_2
If this is a unitary process then the duplication of the bases elements
χ_1 + bχ_2 → a^2χ_1χ_1 + b^2χ_2χ_2
would be equal, and clearly it is not.
A Hadamard gate is not a unitary operation, and so one can prepare or duplicate states that way.
Nevertheless It has been proven you could theoretically make a arbitrary large quantum computer even if the underlining quantum gate had a error rate as high as 3%, although the amount of overhead needed for error correction would be so large it probably wouldn't be practical. But the overhead drops fast with increased gate reliability, if you can get the error rate down to 1% then it looks like a Quantum Computer of arbitrary size is practical as well as possible.
This is if your QEEC to operate fast enough. I think the optimal QEEC is based on the Jordan matrix algebra with 3 E8 groups. This is a stabilizer of the Fischer-Griess group. All possible groups or their generating algebras can be embedded.
> for now quantum computers are in a bit of a niche market of sorts, and their practical use is largely with encryption.Somebody will certainly use Shor's factoring algorithm to break RSA encryption once they get their hands on a Quantum Computer, but I think the killer application will be in efficient quantum simulation; imagine dreaming up a complex shape you want a protein to fold up into and the computer telling you what sequence of amino acids will fold up into exactly that shape. It would revolutionize medicine and chemistry not to mention give a big shot in the arm to Drexler style Nanotechnology.
Or quantum gravitation, which is what I am interested in simulating. I have certain hypotheses about entanglements with quantum black holes that I want to in a sense "test."
> I do though suspect before long ordinary computers will have some qubit processor that will be executed in some algorithms.Maybe but I doubt it. Nobody knows if a conventional computer could solve all nondeterministic polynomial time problems in polynomial time, we don't even know if a Quantum Computer can do that, but there has been a recent development that I find suggestive. Even if, to everybody's surprise, it turned out that P=NP and even if we had a algorithm that could solve NP problems on a conventional computer in polynomial time there would STILL be a class of problems a conventional computer couldn’t solve efficiently but a quantum computer could. Yes this class of problems is very exotic and nobody knowns if they have any fundamental interest in themselves or if they're interesting only because a conventional computer can’t solve them, but still...John K Clark
The computer of the year 2030 will have a network of processors. There will continue to be a straight up von Neumann type processor, but what can run in parallel with neural networks, quantum processors and other specialized processors. The Ras-Tal theorem illustrates a reduction in the need for oracle input.
LC
John Clark
Jun 22, 2019, 12:08:50 PM6/22/19
to everyth...@googlegroups.com
> A Hadamard gate is not a unitary operation
I don't quite understand that. I thought all quantum logic gates could be represented by a symmetric Hermitian matrix, and if all the probabilities don't add up to exactly 1 it's hard to see how it could be of much use to physics. What does a probability of 110% mean?
> and so one can prepare or duplicate states that way.
If you could do that then you could get around the Heisenberg Uncertainty Principle. If you could make 2 copies you could measure the position of one particle to arbitrary precision and not worry about velocity, and then measure the velocity of the other copy to arbitrary precision and not worry about position. And they you'd know both position and velocity to arbitrary precision.
It also seems to me that not being able to duplicate a quantum state is the only thing that prevents you from sending messages faster than light. Suppose Alice and Bob are many light years apart and have entangled electrons. Bob makes lots of clones of his electron and measures them, if they're all spin up then Bob instantly knows that Alice has measured her electron, if there is a 50 50 mix then Bob instantly knows that Alice has not measured her electron. Measuring could mean dot and not measuring could mean dash, and presto you've got a faster than light telegraph.
I must therefore conclude that it's impossible for Bob to make lots of clones of his electron.
> The computer of the year 2030 will have a network of processors. There will continue to be a straight up von Neumann type processor, but what can run in parallel with neural networks, quantum processors and other specialized processors. The Ras-Tal theorem illustrates a reduction in the need for oracle input.
I've never heard of the Ras-Tal theorem, I Googled it but all Google could find was your very post mentioning it, Bing couldn't even find that.
John K Clark
Lawrence Crowell
Jun 22, 2019, 6:21:23 PM6/22/19
to Everything List
On Saturday, June 22, 2019 at 11:08:50 AM UTC-5, John Clark wrote:
> A Hadamard gate is not a unitary operationI don't quite understand that. I thought all quantum logic gates could be represented by a symmetric Hermitian matrix, and if all the probabilities don't add up to exactly 1 it's hard to see how it could be of much use to physics. What does a probability of 110% mean?> and so one can prepare or duplicate states that way.If you could do that then you could get around the Heisenberg Uncertainty Principle. If you could make 2 copies you could measure the position of one particle to arbitrary precision and not worry about velocity, and then measure the velocity of the other copy to arbitrary precision and not worry about position. And they you'd know both position and velocity to arbitrary precision.It also seems to me that not being able to duplicate a quantum state is the only thing that prevents you from sending messages faster than light. Suppose Alice and Bob are many light years apart and have entangled electrons. Bob makes lots of clones of his electron and measures them, if they're all spin up then Bob instantly knows that Alice has measured her electron, if there is a 50 50 mix then Bob instantly knows that Alice has not measured her electron. Measuring could mean dot and not measuring could mean dash, and presto you've got a faster than light telegraph.I must therefore conclude that it's impossible for Bob to make lots of clones of his electron.
Hadamard gates are used to prepare quantum states, to establish or remove entanglements. They are not unitary. I might just come down to Bohr when he said one must have classical operations to measure and understand QM. A Hadamard matrix is such that HH^T = nI, which is sort of close to being unitary.
> The computer of the year 2030 will have a network of processors. There will continue to be a straight up von Neumann type processor, but what can run in parallel with neural networks, quantum processors and other specialized processors. The Ras-Tal theorem illustrates a reduction in the need for oracle input.I've never heard of the Ras-Tal theorem, I Googled it but all Google could find was your very post mentioning it, Bing couldn't even find that.John K Clark
Reply all
Reply to author
Forward
0 new messages