Hitchhiker is on again soon
Just need the Infinite Improbability Drive now.
Google reckons it's on the cusp of demonstrating “quantum supremacy” with the development of a 72-qubit processor. Quantum supremacy refers to the point at which a quantum computer should outperform a classical computer, without incurring the performance costs of error correction (as described in this 2016 paper). Google …
After all, data is king and you know more about us than we do.
Quantum Computing heralds the real BB who knows what we are going to do before we do it.
Google will soon surpass the Governments (if not already) in what they know about us and it is an easy step from there into controlling our every move.
Stop the world, I wanna get off! Google is Evil I tell ye, Evil.
As I understand it, there's terribly few problems whose known complexity is smaller with a quantum computer. In fact, the only that I know is factorizing large numbers. Which sounds very useful to destroy cryptography, until you remember that elliptic-curve cryptography is not affected, so we can just change algorithms and carry on...
So really, what's the use of quantum computers?
The classic example of where classical computers don't work too well is called The Travelling Salesman problem - ie what's the most efficient route to visit all the cities. Some quantum computers could calculate all possible paths *simultaneously*. But beyond optimising supply chains and logistics, other applications for quantum computers include research into materials and medicine.
Some scientists doubt if quantum error rates can be reduced sufficiently, but it's too big a prize to not reach towards.
"Some quantum computers could calculate all possible paths *simultaneously*. "
How are they programmed for that? Where is the database of cities and routes stored and in what form? How do you change the programming to make it crack an encrypted message or solve a crossword puzzle?
These are the questions I've always asked and nobody ever seems to be able to answer them.
> How do you change the programming to make it crack an encrypted message
Shor's Algorithm. Basically, a way to factorise large numbers in a sensible time frame if you have a quantum computer. Using classical computers it is very time consuming to factorise large numbers, whereas it is trivial to multiply numbers - it is this asymmetry that forms the basis of most encryption schemes in use today.
https://en.m.wikipedia.org/wiki/Shor%27s_algorithm
No! The class of algorithms efficiently computable by Quantum Computers (i.e. BQP) does NOT include NP-hard or even NP-complete problems.
To be pedantic: If you can prove your statement, you have a million dollars waiting for you.
I think what you mean is that BQP is not known to include NP-complete problems.
https://en.m.wikipedia.org/wiki/Shor%27s_algorithm
"The quantum circuits used for this algorithm are custom designed for each choice of N and each choice of the random a used ..."
So, custom hardware or perhaps something similar to a PGA (Programmable Gata Array) if they can incorporate the reconfiguration elements/switches?
These are the questions I've always asked and nobody ever seems to be able to answer them.
You need an Ashkenazi brain to grog this. Thumbs up for "Jewish Science". (JOKE! JOKE! HEEELP!)
Just remember that it's not a digital computer. Approach it the same as an analog computer.
In the meantime, if you can do linalg: Quantum Algorithms via Linear Algebra (unfortunately still not read, as I have to deal with management algebra mostly)
The blog to read about this stuff is Scott Aaronson's. At least, some of it.
https://www.scottaaronson.com/blog/
If you can't face that, just read the yellow text in the header:
"If you take just one piece of information from this blog: Quantum computers would not solve hard search problems instantaneously by simply trying all the possible solutions at once"
Or you could try to get a slightly more detailed gist from this comic:
https://www.smbc-comics.com/comic/the-talk-3
So... qubits have "amplitudes" instead of probabilities...? Yeah, and Ogres have layers like onions. It's unbelievable that nobody manages to put three articulate paragraphs together on the subject without careening off into "Hilbert space" whatever that is! Screw this! Oh, Feynmann, where art thou?!?
Nobody will EVER give you such answers. Instead they'll refer you to pure maths papers or lectures, in which abstract mathematical concepts are discussed. But implementation? Means, methods? Practical info? No chance. After all, quantum computing is homeopathic IT.
Nobody will EVER give you such answers. Instead they'll refer you to pure maths papers or lectures, in which abstract mathematical concepts are discussed. But implementation? Means, methods? Practical info? No chance. After all, quantum computing is homeopathic IT.
Horseshit.
Even the Wikipedia articles on Grover's and Shor's are quite readable, if you have some fairly basic mathematical knowledge and the ability to focus your mind for a few minutes.
I'm not a big proponent of QC myself. We're still far, far away from practical hardware, much less hardware cheap enough to be used on more than a few specific problems. And as N posters above have pointed out, while problems known to be in BQP isn't a trivial set, it's not everything we'd like to be able to solve, either.
But the basics are not that difficult to understand, and they are founded on uncontroversial physics and mathematics, and they've been demonstrated at small scale.
I MIGHT, POSSIBLY be able to help!
On a pure and practical basis, a TRUE Quantum Computer CANNOT be created by 2018-era technology because we are NOT able to read the CURRENT state AND position at the same time of an entire atom much less its constituent parts like electrons, quarks and/or other "Quanta".
So how do we create a classical Von Neumann computer architecture out of SMALL things such as atoms?
1) Take a Xenon atom (or any OTHER noble gas atom such as Neon, Argon, etc!) and trap one or two atoms (or even paired molecules) within a confinement field that is placed inside of a small hole drilled onto a common CMOS or high-speed GaAs (Gallium Arsenide) chip!
2) Confinement field should be electromagnetic (or one of the other 3 forces if we humans ever get up to that level).
3) Pulse a femto-second laser at said trapped atoms (or atom pairs) and measure spin OR position within the well.
4) Define 3D-XYZ Octants within the cubic area of the drilled holding well and confinement field of CMOS or GaAs chip.
Front Upper Left-side = 0;
Front Upper Right-side = 1;
Back Upper Left-side = 2;
Back Upper Right-side = 3;
Front Lower Left-side = 4;
Front Lower Right-side = 5;
Back Lower Left-side = 6;
Back Lower Right-side = 7;
Now you have defined a THREE BIT value that is represented whenever the Xenon atom is found to be ANYWHERE within the octant when pulsed by the READING laser. The WRITING laser which is higher powered, PUSHES the Xenon atom to a specific PART of the octant and the electromagnetic confinement field will KEEP IT THERE thus preserving its "Written" value!
5) So from three bits of data, you can define ANY OTHER data type such as a signed or unsigned integer, a fixed point number, a floating point number, a character or a string of ANY bit-length when you combine it with other "Quantum Wells" which then represent the larger, more complex data types!
Since a femto-second laser can be pulsed at around a minimum of 2/1,000,000,000,000,000ths of a second or two-quadrillionths of a second (i.e. the reciprocal frequency of light) it means that quantum well could be theoretically set with new values at about 500 TRILLION times per second. Multiply THAT single well by say the 4 Billion Wells (which what would fit on a modern CPU chip the size of an Intel iCore7) and your TOTAL DATA RATE is in the range of 2 to the 24th power which is AN ENORMOUS amount of data!
6) NOW that is just DATA STORAGE! Since Quantum Wells can ALSO be used as a TRANSISTOR (i.e. a gate or a switch), it means I can emulate ANY TYPE of generic CPU processing on that combined series of Quantum Wells. (i.e. you can EMULATE the passing through OR NOT, and the re-direction of various bit-patterns which forms an emulation of an electrical flow!)
The actual EMULATED CPU processing speed would likely be on the order of 100 TRILLION CYCLES per second if I used Femto-second lasers. ...AND... that is only ONE SINGLE CPU !!! If I make a system containing 1000 quantum-well based CPUs, I could put a multi-ExaFLOP supercomputer in a box the size of a beer fridge !!!
7) NOW....if we use more unstable and/or FASTER atoms or their SUB-ATOMIC constituents (i.e. Quarks), then I could use Attosecond lasers to get many Quintillions of CPU Cycles per quantum well array AND make them SMALLER to boot! This means I could put ZettaFLOPS of CPU horsepower into the size of a closet! A ZettaFLOP computer (10 to the 21st power!) would be able to do WHOLE BRAIN EMULATION down at the molecular level of THOUSANDS of human brains each with the equivalent of having multiple PhD's in various disciplines! What I could do with THAT SORT of supercomputing horsepower fitting in a space much smaller than my flat (apartment) would be BEYOND IMAGINING!
Of course, to MOVE and/or COPY the values of stored data bits from one quantum well to another, your TRANSFER medium NEEDS to be a pure optical signal (UV lasers work great!) to keep the benefit of the high-speed nature of Classical computing using Quantum Phenomena.
A TRUE quantum computer which allows measurement of BOTH position AND spin is probably 50 years away due to the Quantum Decoherence problem where by READING a spin AND position value value we destroy its position and/or spin BUT we can get NEARLY the same speed-up by scaling up to atomic-levels and EMULATING classical computing based upon the reading of or setting of spin OR positional states of trapped atoms within a small well drilled into common CMOS or GaAs substrates.
.
I hope that helps...
.
Comments and Questions are MOST Welcome!
Now to answer the question of "What is the Practical Application of a Quantum Computer?"
There are FOUR PRACTICAL answers:
1) Break other people's encryption so we can then wire ourselves a SWIFT account transfer of 100 million Euros so we may spend it day and night on all things Possibly Immoral, Likely Illegal and Most Definitely Fattening!
2) Emulate a Human brain at the molecular level so that we may achieve TRUE General Artificial Intelligence (i.e. have a 1000 PhD's at your beck and call working day and night on ANY and EVERY intellectual problem you throw at them!)
3) Emulate MULTIPLE X-Boxes AND Playstations running all at the same time, and each running at ExaFLOPS+ so we can play CRYSIS at max 64k x 64k resolution at 1000 fps and 64x Anti-Aliasing!
4) Make Siri or Alexa COME ALIVE FOR REAL and do the things I dream about..........ONCE they design and genetically engineer a REAL AND FAST-GROWN PHYSICAL BODY TO MY FULL Double-D SPECIFICATIONS OF COURSE !!!!!
The classic example of where classical computers don't work too well is called The Travelling Salesman problem - ie what's the most efficient route to visit all the cities. Some quantum computers could calculate all possible paths *simultaneously*.
No! The class of algorithms efficiently computable by Quantum Computers (i.e. BQP) does NOT include NP-hard or even NP-complete problems.
Some scientists doubt if quantum error rates can be reduced sufficiently, but it's too big a prize to not reach towards.
Yes indeed: The Future of Quantum Computing (Hope this goes through, sometimes Forum Control™ takes a dislike links to Quanta Mag, I suppose it's on the list of the false-newsy sites somehow)
>> elliptic-curve cryptography is not affected
Don't tell NIST [https://nvlpubs.nist.gov/nistpubs/ir/2016/NIST.IR.8105.pdf] as they say ECDSA and ECDH (Elliptic Curve Cryptography) are both "No longer secure".
And don't tell the NSA [https://www.schneier.com/blog/archives/2015/08/nsa_plans_for_a.html] who are recommending against migrating to Elliptic Curve cryptography.
Guess what bitcoin uses to control access to your funds? ECDSA of course. So you can fund that quantum computer from the bitcoins released once you crack everyone's public keys on it.
"So really, what's the use of quantum computers?"
I'm interested in predicate logic engines. Predicate logic is glorious at working solutions out for itself, but lousy at working out which of its many possible routes it should do first, and burns large amounts of time exploring dead ends. If you can explore multiple deadends at once, this could be be very useful.
On the other hand you probably need to load the whole question to collapse it into an answer, but if anyone's good at scaling things it's Google. They can probably quantum link cloned machines via fiber and entangled photons or something.
Your understanding is incorrect.
Relatively few problems have known efficient solutions with a quantum computer, but that isn’t the same at all.
The key point is that a QC can execute at least one NP-hard problem in polynomial time. There is a theorem similar to the Turing computability theorem for Turing machines that shows that *any* NP problem is solvable in polynomial time if you can solve any other one. Almost all “interesting” hard problems are known to be NP complete.
However.....
A) The proof is not constructive, it just says it can be done
B) Those that have been found often still have nasty complexities. O(N43) is still brutal even if it is polynomial
In the example of ECC you gave, you are exchanging the current situation where (almost) all mathematicians are very sure there is no way to do it because it is proved NP hard (but haven’t managed to prove NP NE P). For a situation where they all know it is possible (but haven’t yet had an incentive to work on it because the first assumption isn’t met).
Relatively few problems have known efficient solutions with a quantum computer, but that isn’t the same at all.
The key point is that a QC can execute at least one NP-hard problem in polynomial time.
No! NO! NO!!1!
There is not, I repeat, not a single NP-hard problem for which we have found an algorithm solving it in polynomial time. Even with a quantum computer.
To quote the Wikipedia article on Quantum Computing: "There is a common misconception that quantum computers can solve NP-complete problems in polynomial time. That is not known to be true, and is generally suspected to be false."
The proof is not constructive, it just says it can be done
The proof is constructive, just impractical.
RF questioned, "...elliptic-curve cryptography is not affected..."
The history of math(s) is littered with sudden and unexpected connections popping up where one field is suddenly made precisely equivalent to a completely "unrelated" field.
So when Dr. Christian Szell asks you, "Is it safe?", the future-proof correct answer is, "Presently yes. It is very safe. But in the longer term, probably not. So be very cautious."
NO NO NO!!!! NO Elliptic Curves !!!
Multivariate, Lattice and single-use codes, etc. would be resistant (not necessarily break-proof!) against quantum computing machines (i.e. Dwave et al...) that use All-States-At-Once computation which "Anneals" down to a credible and/or likely single or series of "Answers". Using Shor's and Grover's algorithms against AES, DES, RSA ...AND.... Elliptic Curve-based cryptography WILL eventually break those indicated encryption algorithms....so again NO ELLIPTIC CURVES !!!! Just Don't Use Them!!!!!
Make sure every message can be decrypted into multiple results. ;)
Every message can be decrypted into multiple results. Any given message can be decrypted into any given plaintext by some algorithm - in the degenerate case, by a constant function that returns the desired result for any input.
More seriously, there's a long history of deniable encryption, where multiple plausible plaintexts are possible with close to equal probability. There was particular interest in this area around encrypting filesystems, so (for example) you could have a partition which decrypts into innocuous data with one key, and sensitive data with another.
Obviously (by the pigeonhole principle) there's some additional storage cost, even with compression.
To expand Mage's point, it's common practice for the NSA to archive encrypted intercepted communications - they can't be decrypted now, but could be in future. What use is years-out-of-date intelligence? It can give you valuable context about your enemy and insight to your thinking. .... Dave 126
Hmmm? Such common practice also gives, Dave 126, invaluable precious enemy intelligence oversight of the NSA [and all other similarly run agencies] because of its failures in thinking, and with the realisation of catastrophic live vulnerabilities for both present and future exploitation with current encrypted intercepted communications and 0day programming trades, are they rendered to be forever battling past daemons and fleet of foot phantoms which are further designed to intelligently crash and almightily bankrupt their SCADA Systems/Elite Exclusive Executive Operations.
Surely any Secret Intelligence Service worthy of being so named is more into the providing and utilisation in applications of new future information which is not years out of date. Neither time nor space wait in line patiently for the past to create presents in the future ..... and neither do smarter beings doing Global Operating Devices work on Earth.
And if that be a TS/SCI Problem, so be it and so what, whenever you can do absolutely nothing about it and just have to accept it and the new ....... well, some would call it Reality whilst others would claim it AI Virtualised Reality with Novel Running ProgramMING Projects.
Can you imagine those Projects being run by your currently thought to be enemies and the costs incurred in failing to successfully deal with them? Methinks Trillion$ is not even close to the price to be paid to ensure one is not defeated and overwhelmed. And if you be real lucky and quick on the draw, DaneGeld in the Billion$ may be an acceptable price to pay to Novel Running ProgramMING Projects Managers to mothball and keep secret their Operations/Missions and Modi Operandi.
Supposing "qubit density" doubles every 18 months Moore's-law-style, quantum computers will be practical in a bit over 16 years.
s/practical/possible
Google's Bristlecone isn't exactly commodity hardware.
But that said, yes, if a similar exponential growth rate in qubit density applied, we'd have at least one working physical implementation of a "practical size" QC with sufficiently low error rate within 20 years.
That was essentially Mosca's prediction back in 2015. (I don't have the citation handy but it's cited in the NIST paper someone mentioned above.)
Personally I'm pretty dubious - increasing qubit density isn't just a matter of better lithography methods and materials, as it was for conventional silicon - but who knows? I've been wrong at least once or twice before, though this may be due to errors in the universe.
A problem of engineering?
Looking at the lasers and setups in labs, it's just a problem of practical engineering. Nothing really stopping us making a GIANT Colossus style lab with tons of lasers and inforemeters and cooling... given enough need.
We don't have that need, so spending the resources shrinking and simplifying the design, so we can have 100s or thousands of chip sized QC systems is much more resource efficient.
So I guess we are at just before the Babbage Machine stage? So a 100 years or so before hand held quantum computers? (Though adding the "Cloud", we could remotely connect to them in 50 years?)