A quantum computer is a device that exploits constructive and destructive interference among exponentially many amplitudes, which are numbers that are closely related to probabilities but can be positive, negative, or even complex.

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. :-)

Here's my attempt at a two sentence over-over-over simplification that at least gets people away from the "magic bit-sting that contains your answer." (It also harkens back to an old Einstein quote, so may be attractive to science writers.)

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.

Do you mean all the possible solutions to a problem when you say 'answer space' ?

That's how I would interpret it, yes

Wow, that was nice and succinct.

"Loaded dice ", I have not heard that before... Is it same as Biased dice

Yes

My favorite quote of yours is that quantum computers "have a profile of abilities so strange that no sci-fi writer would have had the imagination to invent it" - it's a great quote to inspire people to dig deeper into the (literally beyond classical imagination) concepts of quantum mechanics!

In your 35 second blurb, and the New York Times article, it seems like the point you're making is that interference is the main way that quantum computers work. But what makes quantum interference special over other kinds? You can get interference in sound waves, light waves, radio waves, etc. You also mention that magnitudes can be complex, but the same is true of other kinds of waves; complex numbers are used for discussing impedance in electronics.

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?

The difference between QC and all those other examples of interference is that, in the case of QC, the interference happens in configuration space rather than ordinary 3-dimensional space. And configuration space is enormous; it has a dimension that grows exponentially with the number of particles. The number of paths that could interfere with each other to produce a given amplitude is likewise exponential (in that case, in the number of computational steps).

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.

Out of all your replies, I THINK that this is the one that helped me grok why QC is different than somehow simulating quantum math in a classical computer. The idea of being able to tap into more than 3 dimensions sounds like something very fundamental, kind of like relativity, and a key aspect of how our universe works that at least I was never aware of (and probably a lot of other people!)

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?

Pretty much any intro to QC (and in particular, any of the intros I've written, and linked to elsewhere on this thread) will make the point about Hilbert space (that's what it's called) having a dimension that grows exponentially with the number of particles in your system. This is because every possible classical configuration of the system is its own orthogonal "direction" in Hilbert space, and the full state can be an arbitrary superposition (i.e., complex linear combination) of those directions.

Ok, I'll try another attempt at explaining the stuff :P Not sure if correct, because I'm not a parent :P neither a quantum scientist actually, just dabbled a tiny bit in QC at one point :) So you can choose whether to believe my words or not :)

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 :)

As someone still trying to understand the essence of quantum computing, your analogy to me can be summed up as coherence only comes from coherence. Which to me is too general, and describes computing as a whole. How coherence is determined in the particular case of quantum computing as opposed to classical computing is the meat and potatoes that I'm looking for.

Sorry, don't think I can do more at this point; I once managed to understand the Shor's algorithm from some book; but I didn't reinforce it, and now I'm left only with a vague recollection of the main a-ha moment... Though I actually don't really get what do you mean by coherence here (esp. in the area of classical computing).

My coherence I mean something intelligible that can be acted on (ie. computer code and its results).

“Quantum Computing is the exploitation of quantum state evolution to perform computation.”

A quantum computer is a high-tech ouija board.

If you post like this again we will ban you.

I'll just point to this https://www.smbc-comics.com/comic/the-talk-3 which was posted as an answer to a similar question I had on a previous discussion about a blog post of his.

That was fantastic and enlightening, thank you.

Ditto, fun read thanks for sharing.

Exactly the question I would love answered.

Edit: this seems roughly answered to a question by user r4um

I don’t see where it’s answered?