100 qubit comps would change everything:

https://thenextweb.com/artificial-intelligence/2018/02/06/heres-why-100-qubit-quantum-computers-could-change-everything/

That was one question I asked, and it seems now we are approaching 20 qubits so I guess we have a way to go to get to 100. I thought someone said we would need a thousand or more qubits to get something more powerful than the fastest most powerful classical computers on the planet.
So wouldn't it be a natural next step to combine the fastest classical comps to such a 100 qubit machine for even more usability and wider range of problems the pair could tackle?

Originally posted by @sonhouse
https://thenextweb.com/artificial-intelligence/2018/02/06/heres-why-100-qubit-quantum-computers-could-change-everything/

That was one question I asked, and it seems now we are approaching 20 qubits so I guess we have a way to go to get to 100. I thought someone said we would need a thousand or more qubits to get something more powerful than the fastest ...[text shortened]... h a 100 qubit machine for even more usability and wider range of problems the pair could tackle?

Quantum machines are believed to be able to solve a class of algorithms in polynomial time, which are in the class NP (I think the class is called BQP or some such). The classic example is factorizing a composite number. The factorization problem is in NP, meaning that it cannot be solved in an amount of time that is a polynomial function of the size of the input on a Turing machine, in other words on a classical computer, but once a solution has been found it can be checked in polynomial time on a Turing machine. So, once a factorization has been found one then uses a classical machine to check the output of the quantum machine. The 'B' in BQP stands for bounded error and the 'Q' for quantum, the P is polynomial. So a quantum machine can find a solution to the factorization problem in polynomial time, which has a finite, but bounded (say less than 1/3) probability of being wrong - this is why the answer needs checking. So connecting a quantum machine with classical ones is mandatory - one has to check that they've got the answer right.

Originally posted by @deepthought
Quantum machines are believed to be able to solve a class of algorithms in polynomial time, which are in the class NP (I think the class is called BQP or some such). The classic example is factorizing a composite number. The factorization problem is in NP, meaning that it cannot be solved in an amount of time that is a polynomial function of the size ...[text shortened]... m machine with classical ones is mandatory - one has to check that they've got the answer right.

It seemed obvious the two should be used together. I didn't know the answer was only accurate to within 66%. Does that change if you up the # of qubits? So it sounds more like the old analog computers which in my day I actually worked on. My engineer was Horst Schlingloff, a German, and we were at Goddard Space Flight Center and my job there was wiring the 1728 tie points making up the analog computer 'program', just tie points say hooking up output A to integrator B, thence to op amp C and so forth.
Took a couple of weeks to do that job.
Horst engineered a way on a more 'modern' analog machine to be controlled by a digital computer, which ATT was programmed with punched cards but it was a lot faster to make the programs for the digital comp which then was wired to control the servos of the analog machine which made MY job a lot easier🙂
One patch setup I wired was for an engineering study of masses stuck around the inside of a cylindrical shaped satellite spinning, if the masses would force the cylinder to wobble. That was the one job my patch panel wiring did🙂 After hooking the tremendous power of the mainframe digital to the analog machine my job went to programmers working with punched cards for the job of the day from design engineers which suited me just fine🙂

It's funny now to think all that could have been done on my android smart phone and a lot more besides! It would have surprised the snot out of old Horst if he could have lived long enough to see all this today.

Originally posted by @sonhouse
It seemed obvious the two should be used together. I didn't know the answer was only accurate to within 66%. Does that change if you up the # of qubits? So it sounds more like the old analog computers which in my day I actually worked on. My engineer was Horst Schlingloff, a German, and we were at Goddard Space Flight Center and my job there was wiring the ...[text shortened]... ve surprised the snot out of old Horst if he could have lived long enough to see all this today.

That 1/3 figure is like 99% of statistics - made up on the spot. I think the actual figure depends on the hardware implementation. I don't think it's affected by the number of qubits. I think that just affects the problem size that can be attempted.

Analogue machines are great. You solve the problem in the time it takes the signal to propagate through the electronics.

Originally posted by @deepthought
That 1/3 figure is like 99% of statistics - made up on the spot. I think the actual figure depends on the hardware implementation. I don't think it's affected by the number of qubits. I think that just affects the problem size that can be attempted.

Analogue machines are great. You solve the problem in the time it takes the signal to propagate through the electronics.

And the time it takes to move servos controlling setting pots, but yes, with only a few decimal points of accuracy but they did the job back in 68

Originally posted by @sonhouse
And the time it takes to move servos controlling setting pots, but yes, with only a few decimal points of accuracy but they did the job back in 68

Fast Fourier Transform algorithms on 32 bit floating point numbers are only accurate to about 1% due to rounding errors propagating through the calculation. So any error less than that's fine.

Originally posted by @deepthought
So connecting a quantum machine with classical ones is mandatory - one has to check that they've got the answer right.

Why not instead just repeat the run of the quantum machine an arbitrarily large number of times to do the same calculation many times and then statistically see which seems to be the most common result?
This would never absolutely guarantee the correct result but it could make the probability of concluding the wrong result so vanishingly small that we can for all practical purposes ignore it.

Originally posted by @humy
Why not instead just repeat the run of the quantum machine an arbitrarily large number of times to do the same calculation many times and then statistically see which seems to be the most common result?
This would never absolutely guarantee the correct result but it could make the probability of concluding the wrong result so vanishingly small that we can for all practical purposes ignore it.

It depends on the complexity class of the problem. If the answer can be checked in an acceptable time that is the best procedure. Problems in the complexity class NP, such as the factorisation problem can be verified in polynomial time, and may as well be. If there are BQP problems which can only be verified in exponential time, or in polynomial time but the polynomial is order N^100, then it's impractical to check the answer, so your strategy of repeatedly doing the calculation on a quantum machine and taking the most frequent solution is the only game in town.

As an aside I checked on Wikipedia and that bound of 1/3 is correct, being part of the definition of the complexity class. However, interestingly, the relationship between NP and BQP is not known, other than they intersect.

Originally posted by @deepthought
It depends on the complexity class of the problem. If the answer can be checked in an acceptable time that is the best procedure. Problems in the complexity class NP, such as the factorisation problem can be verified in polynomial time, and may as well be. If there are BQP problems which can only be verified in exponential time, or in polynomial time ...[text shortened]... ver, interestingly, the relationship between NP and BQP is not known, other than they intersect.

That relationship sounds like a math research project then. Suppose that relationship is resolved, what would that buy you in the quantum world?

Originally posted by @sonhouse
That relationship sounds like a math research project then. Suppose that relationship is resolved, what would that buy you in the quantum world?

I think the priority is working out the relationship between P and NP. I think if P=NP then BQP collapses to P as well. If NP is a larger set than P (it contains it), then BQP may be larger than P. I think the NP hard problems are meant to be outside BQP, but that might be undetermined as yet.

Originally posted by @deepthought
I think the priority is working out the relationship between P and NP. I think if P=NP then BQP collapses to P as well. If NP is a larger set than P (it contains it), then BQP may be larger than P. I think the NP hard problems are meant to be outside BQP, but that might be undetermined as yet.

Is Terence Tao working on that problem?

https://en.wikipedia.org/wiki/BQP

This stuff is clearly way outside my paygrade🙂