Shtetl-Optimized's tagline is famously "Quantum computers would not solve hard search problems instantaneously by simply trying all the possible solutions at once". What phrase do you think should replace 'trying all the possible solutions at once' in the public conciousness as a succinct description of the mechanisms of a quantum computer? Or is this topic simply too complex to be distilled into a neat synopsis while retaining accuracy?
If you feel that sentence wasn't clear enough, and it would take at least a few more paragraphs to flesh it out ... well, duh, what did you expect? :-D
For a SLIGHTLY longer account, see my attempt to explain quantum computing in 35 seconds or fewer, which Maclean's magazine challenged me and others to do in response to Justin Trudeau's quantum computing explanation: https://www.scottaaronson.com/blog/?p=2694
When I did a piece for the New York Times, I managed to get an explanation that I was reasonably happy with into ~6 paragraphs: https://www.nytimes.com/2011/12/06/science/scott-aaronson-qu...
Given that quantum mechanics is, famously, one of the most counterintuitive things that humanity ever discovered, I don't think it's that big of an ask for people to read 6 paragraphs about QC before they decide they basically know what it's about. :-)
Quantum computing is a technique that lets you sample a problem's answer-space using "loaded dice," such that the problem's correct answers correspond with probability spikes in your dice throws. Right now, we only know how to usefully "load" those dice for certain problems, and it's pretty hard to do.
These are even relatively simple to work with; back in high school, I set up my basement as a darkroom, set up a sandbox for isolation, borrowed a laser from my physics teacher, bought a kit online with a beam splitter, mirrors, lenses, and film, and made some holograms of various objects utilizing light interference.
You could set up an apparatus in which light goes through a beam splitter, reflects off mirrors to travel via different paths, and is recombined and interferes in the end to produce an interference pattern. You could probably encode a lot of information in the exact length of the different paths, perhaps in an array of mirrors which could be actuated to produce slightly different path lengths in different parts of the beam (after the beam is expanded), and use the interference to make calculations.
Other than the smaller scale, and greater difficulty of working with it, what is special about quantum interference that would make it more amenable to solving problems that are NP complete than some apparatus producing similar kinds of interference with light?
Also, has it been proven (or argued sufficiently convincingly) that quantum computation at scale is actually possible? I'm wondering if there could be an issue where it requires more computation to construct a quantum computer than the computation you get out, or require a non-constant number of quantum computers (with respect to the size of the problem) to actually get reliable enough results out, or something of the sort.
I think this is somewhat like the questions of whether certain automata are Turing-complete (https://en.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol_T...), when a sufficiently complex process is needed to encode the problem into the automata that it could be argued that the computation was not actually carried out by the automata itself (I don't actually know if that question was answered; Wikipedia references a mailing list thread that has a lot of discussion, but I haven't seen any authoritative conclusion).
Given that empirically, only extremely simple quantum computers have been able to be constructed, what makes us think that there isn't some kind of tricky scaling issue like this were the additional complexity of building, running, or verifying the results of quantum computers will negate the benefits?
No, of course no one has proven that it can work: presumably, the only proof that will convince everyone will be the actual construction of the machines! But in the 1990s, the theory of quantum error-correction convinced almost everyone that, as far as current physics can say, the difficulties (though staggering) seem to be ""merely"" difficulties of engineering. As I discussed in another answer, a deep reason why QC could never be scaled would be MUCH more interesting scientifically than a mere success in scaling it (which would "merely" confirm what physicists already believe). And of course, with the ongoing efforts of Google and others to demonstrate "quantum supremacy" with 50-70 qubits, we're likely to get experimental results that are relevant to your questions within the next few years.
Would you consider writing an in-depth article on configuration space and how it applies to QC (and possibly other research) and sharing it here on HN someday?
Imagine you are a parent/teacher in a room full of happy kids, playing their kid games. Some kindergarten playground or something. They're generally all doing some kind of stuff, and doing it in parallel. Is this "doing work in parallel"? Every one of them is doing something totally else, one kid is building a castle, the other is throwing bricks at it and destroying it ("interference cancelling each other's work"). One is digging holes in a sandbox, another just kicked the sand inside, filling the holes back.
Now, you are just one, insignificant adult in this room. Imagine you would want them to do something for you. Can you just shout at them, "do me some parallel computation"? "Build me a castle of bricks"? Meh, sure you can, but they'll look at you funny, maybe a few of them will start, but their attention will be soon diverted by others, and anyway they'll soon get bored and start fudging around.
But here comes the fun part - if you're a smart and creative teacher/parent/..., you can actually do much better: you can "trick" them into doing your work; you have to either find some kind of a "system", or a "fun game", that they will like, that will fit their abilities and sensibilities, so that they'll choose to generally more or less contribute in the direction you want them to. You have to find a way of doing the task that will be "compatible" with them. Then, collectively, you can actually have them make your work done! But if you don't find the trick - sorry, no free lunch for you :) But you can still keep enjoing watching in awe and wonder how they're having fun, the little buggers... erm, sweethearts :P
In a somewhat similar way, in QC, you have to invent a system that can trick all the qubits, who have their particular, peculiar ways of living and behaving, to contribute to some particular result that will be meaningful and useful to you. Otherwise, they'll totally do some kind of "parallel work", but the result will be just irrelevant mess. To make the challenge even more tricky, you're actually outside the room when the work is happening. You don't see the "calculation" ([wavefunction] vector) each kid... umm, qubit is contributing, you only see the one final result. Nah; that would be too easy still; you can only see the shape of the result's shadow (just the length of the final vector).
(edit: ah, and I forgot the most important thing: if I'm not wrong, each extra kid is are actually contributing exponentially more work; if you have N qubits, you are trying to trick 2^N vectors to work for you)
Sorry for still being very vague and handwavy :)
Hmm, one more vague analogue could be to "computer proof systems/theorem provers", e.g. Idris, or trying to prove/enforce something with GADTs. You have this set of rules/mechanisms; now, you have to sit and squeeze and tear your brain in different ways to invent how to force those limited rules to encode the thing you want to prove. Not easy. But sure a challenging and potentially fun brainteaser :)
Edit: this seems roughly answered to a question by user r4um