The optimization mode requires quantum effects, can solve a growing list of problems.
See full article...
See full article...
A quantum computer that has an alternative problem-solving mode
- Thread starter JournalBot
- Start date
Thank you for the article John. Would you be able to do an article on "Quantum Sensors/Sensing"?
Upvote
13
(13
/
0)
Many, many problems can be cast as optimization problems. (See the vast literature on optimal control.) Transforming them into something this beast could work on might spawn more than a few Ph.D. theses...
Upvote
27
(27
/
0)
I'm assuming that should be 'excite'? (Mind you, it's quantum mechanics, If I found there was a little electron fire door that they could leave through, that wouldn't suprise me either).
Upvote
38
(38
/
0)
I still can't quite wrap my head around the idea that they are manipulating individual atoms, let alone putting them into computationally useful configurations. "Any sufficiently advanced technology is indistinguishable from magic."
Upvote
46
(46
/
0)
Can anyone comment on the impact on the results if you don't have perfect 1/3, 1/3, 1/3 odds in a triangle configuration because you're not in a perfect equilateral triangle? That just pulls us off the peak a bit?
Upvote
6
(6
/
0)
Can we have some $$ numbers? Just curious as to what numbers we are talking about for owning or "paid access"...
Upvote
6
(6
/
0)
IBM Charges $1.60 per qubit-runtime second
https://www.ibm.com/quantum/access-plans
AWS has a more convoluted model:
https://aws.amazon.com/braket/pricing/
Upvote
19
(20
/
-1)
It will provide other answers as well - but they'll all have much lower probabilities than "4."
Upvote
19
(19
/
0)
From the article:
Surely that should be "the qubit count is too low, and the error rates are too high".
Surely that should be "the qubit count is too low, and the error rates are too high".
Upvote
11
(11
/
0)
I doubt we'll see any of those in Computer Science, given this is pretty well trodden ground already. Its something you do in your algorithms course at the undergraduate level.
But this is why theory is important. When a novel tool like this shows up, we already know exactly how to make good use of it.
Upvote
8
(8
/
0)
So is it a race between a useful quantum computer and a financially viable fusion reactor? Fusion had a massive funding head start but I'd put my money (if I had any] on quantum computers.
Upvote
8
(8
/
0)
Feynman’s book The Theory of Fundamental Processes is helpful background reading. It emphasizes the very few principles of quantum mechanics, and how these enable quantum processes to be analyzed and understood very simply and sound intuition to be developed. There is some heavy-ish mathematics when some quantum calculations are done, but getting to an understanding of what calculation is needed proceeds mostly purely by reasoning using the physical principles.
The principles based character of the book is similar to that of Einstein’s paper On the Electrodynamics of Moving Bodies.
The principles based character of the book is similar to that of Einstein’s paper On the Electrodynamics of Moving Bodies.
Upvote
6
(6
/
0)
Upvote
6
(6
/
0)
Traveling salesmen will soon be able to save some gas money when planning their routes.
But seriously this seems like big news that will allow a positive feedback cycle. Immediate utility will help push more investment in developing quantum computers which will lead to more applications which will lead to more investment in development.
I'm interested to see what the killer app for quantum computers turns out to be. Or maybe quantum computers will be like lasers where they will have a surprising number of uses in everyday life as well as enabling other technology.
But seriously this seems like big news that will allow a positive feedback cycle. Immediate utility will help push more investment in developing quantum computers which will lead to more applications which will lead to more investment in development.
I'm interested to see what the killer app for quantum computers turns out to be. Or maybe quantum computers will be like lasers where they will have a surprising number of uses in everyday life as well as enabling other technology.
Upvote
14
(14
/
0)
There was recently some buzz about DWAVE solving some logistics problems; or at least, getting a good solution fast, which is probably good enough. I love this. It's a whole new angle of attack on problems that are known to be digital-computer difficult, and it's coming about in my lifetime. Very exciting.
Upvote
5
(5
/
0)
Back to the Future redux ala the dawn of mainframes where 500k memory was millions of dollars that corps splurged to automate the entirety of its soul.
Being scalar architecture, it’ll be interesting when qubits find their airline reservations application that mainframes conquered.
Being scalar architecture, it’ll be interesting when qubits find their airline reservations application that mainframes conquered.
Upvote
3
(3
/
0)
Great article.
One of the challenges for solving this type of problem is not just how long it takes to solve on a quantum computer but also the set up time. When solving for where to put a new building you have weeks, maybe months to solve the problem. To solve the problem of where each FEDEX driver goes on a day, you have less than seconds to solve the problem. You have to configure your quantum computer for each run. That setup time has to be short. Loading data into a qubit is not anywhere near as fast as loading data into a computer.
One of the challenges for solving this type of problem is not just how long it takes to solve on a quantum computer but also the set up time. When solving for where to put a new building you have weeks, maybe months to solve the problem. To solve the problem of where each FEDEX driver goes on a day, you have less than seconds to solve the problem. You have to configure your quantum computer for each run. That setup time has to be short. Loading data into a qubit is not anywhere near as fast as loading data into a computer.
Upvote
8
(9
/
-1)
I don't see why setup time would not be part of how long it takes to run the program. It would be like not counting data stalls against the runtime of an algorithm in a conventional CPU.
That also isn't quite right for your analysis of the FEDEX driver. They literally have hours over night to determine what the route is, once they've decided what packages should be on the delivery truck. The question is if it is cost effective to do this analysis on the hardware, as this is an application where it makes sense to rent time on hardware, since they won't use it for more than 4 to 6 hours a day. You'd only need enough power for recalculations when something goes wrong during the day.
Upvote
7
(7
/
0)
This was, to a degree, also DWAVE's strategy. They started off with analog quantum computer that can do optimization problems. But the plan was always to leverage the engineering expertise they gained from building the optimizer to build a digital quantum computer.
Upvote
7
(7
/
0)
Well, you aren't calculating just one route are you? You have a small number of quantum computers to calculate 10's of thousands of delivery routes??
Upvote
0
(0
/
0)
Major misunderstanding on NP-Complete.
Here is the situation: If you could solve an NP-C problem, then you could solve any NP-C problem (which are all the hard problems).
BUT it is unlikely that any NP-C problem will ever be solved, so none of this does you any good.
Here is the situation: If you could solve an NP-C problem, then you could solve any NP-C problem (which are all the hard problems).
BUT it is unlikely that any NP-C problem will ever be solved, so none of this does you any good.
Upvote
0
(1
/
-1)
"machines that don't currently have a clear delivery date. It could be years; it could be decades."
You forgot to add: "could be never".
There are multiple Quantum Computing breakthroughs every week. But we are still no closer to a Quantum Computer that actually does anything other than contrived toy problems the developers cobble up to try to show that the thing works. Supposed actual QC results are generally examined by experts, who quickly find a faster way to do it with a PC, or probably a smartphone, play station, or whatever.
Is there any reason why QC might never work? One argument is the "100 mile stack of quarters" example. It goes like this:
You can put a quarter (US $0.25 coin) on your desk - no problem. Then you can put another quarter on top of it to make a 2 quarter stack - no problem. Once you have n quarters on the stack, put on another quarter to have a stack of n+1 quarters - no problem. Keep this up until the stack of quarters is 100 miles high.
What could possibly go wrong?
You forgot to add: "could be never".
There are multiple Quantum Computing breakthroughs every week. But we are still no closer to a Quantum Computer that actually does anything other than contrived toy problems the developers cobble up to try to show that the thing works. Supposed actual QC results are generally examined by experts, who quickly find a faster way to do it with a PC, or probably a smartphone, play station, or whatever.
Is there any reason why QC might never work? One argument is the "100 mile stack of quarters" example. It goes like this:
You can put a quarter (US $0.25 coin) on your desk - no problem. Then you can put another quarter on top of it to make a 2 quarter stack - no problem. Once you have n quarters on the stack, put on another quarter to have a stack of n+1 quarters - no problem. Keep this up until the stack of quarters is 100 miles high.
What could possibly go wrong?
Upvote
-2
(1
/
-3)
I know, it's like a shell game virtuoso is at the helm. "Step right up. Get as close as you like. Now follow the nuclear spin state!"
I'm glad there are articles like this that allow me to initiate beginning to start to sort of maybe understand a tiny little iota of quantum mechanics, because it's fascinating.
Upvote
2
(2
/
0)
You can certainly solve NP problems, it just can't be done in polynomial time (though a solution can be checked in polynomial time). So as the size of the problem - e.g. the number of towns a travelling salesman must visit in the NP-C version of the problem - goes up, the time to guarantee the best solution by way of standard computation rises exponentially.
The 'complete' means that an NP-C problem is part of a large class of NP problems each of which can be mathematically transformed into any other of the class. So if you found a non-exponential (i.e. polynomial) way to solve one, you would have a non-exponential way to solve them all (the transformation might be clunky, but if the problem gets large enough it's the exponential difficulty that matters).
It's pretty certain that there is no such polynomial solution. It's probably impossible to prove it.
Last edited:
Upvote
5
(5
/
0)
The article does not even grt the most fundamental facts right. For example, the maximum weight independent set problem is NP-hard, not NP-complete. That is a big difference. And one might be able to transform any NP-complete problem into each other one, but that is often completely impractical, because the problem size is only polynomially bounded. Meaning that if you have a problem with n variables, the corresponding other problem might have something like n^100 variables.
Upvote
2
(2
/
0)
My understanding is that, like the travelling salesman problem, it can be converted into a decision problem that is NP-complete. Wikipedia has a list, on which it appears.
You are of course correct that (i) the complexity class of a problem doesn't tell us anything about whether we can solve it in cases of a size that concern us, and (ii) the transformation from one problem to another might be prohibitively expensive at useful problem sizes.
Upvote
2
(2
/
0)
Yes, some decision variants can be used to solve the optimization variant, but that comes with additional costs. You need to ask something like: is there a solution of weight <= x? And then find the minimum such x by binary search (assuming you have rational data). Meaning that you might have to solve the decision problem many times.
I spent 5 years of my life to develop algorithms and software for the Steiner tree problem (a classic NP-hard problem). I can solve huge problems to optimality. With millions of variables.
But it does not mean at all that I can solve other NP-hard optimization problems efficiently, even though their decision variants can be transformed to Steiner tree problems.
I spent 5 years of my life to develop algorithms and software for the Steiner tree problem (a classic NP-hard problem). I can solve huge problems to optimality. With millions of variables.
But it does not mean at all that I can solve other NP-hard optimization problems efficiently, even though their decision variants can be transformed to Steiner tree problems.
Last edited:
Upvote
0
(0
/
0)
Thanks John for the well-written and comprehensible article. Keep it up!
2. It doesn't matter, there is no intersection between the sets "people who get time on quantum computers" and "people who would try to use one for arithmetic."
(And yes, your comment is funny, I just wouldn't want it to mislead anyone.)
1. No.
2. It doesn't matter, there is no intersection between the sets "people who get time on quantum computers" and "people who would try to use one for arithmetic."
(And yes, your comment is funny, I just wouldn't want it to mislead anyone.)
Upvote
0
(0
/
0)
Quantuum Chess,Can They Play Each Other
I've cant really see the signifigance of the open slit experiment. Because a thing is a wave or a particle. I must say I looked for a story so I could post this.
There is a signifigance in some of the probability mathmatics. But superposition,using the idea escapes me.
Here for this,would seem to have a prudent idea to simply have two different quantuum machines,each be an opponent to each as chess players.
Watch the game,and see that the AI works from them. Have most of the elements discussed with this article,- geometry,mathmatics,probability. And an equal base field to begin with.
Earliest AI was those dealing with automatic chess routines. Unlike loading 'all previous moves. These players have only their own memories to fill,..
Hope that microcosim is looking out for new physics on those small scales.
I've cant really see the signifigance of the open slit experiment. Because a thing is a wave or a particle. I must say I looked for a story so I could post this.
There is a signifigance in some of the probability mathmatics. But superposition,using the idea escapes me.
Here for this,would seem to have a prudent idea to simply have two different quantuum machines,each be an opponent to each as chess players.
Watch the game,and see that the AI works from them. Have most of the elements discussed with this article,- geometry,mathmatics,probability. And an equal base field to begin with.
Earliest AI was those dealing with automatic chess routines. Unlike loading 'all previous moves. These players have only their own memories to fill,..
Hope that microcosim is looking out for new physics on those small scales.
Upvote
0
(0
/
0)