Quantum Algorithm Beats Classical Tools On Complement Sampling Tasks (phys.org) 34
alternative_right shares a report from Phys.org: A team of researchers working at Quantinuum in the United Kingdom and QuSoft in the Netherlands has now developed a quantum algorithm that solves a specific sampling task -- known as complement sampling -- dramatically more efficiently than any classical algorithm. Their paper, published in Physical Review Letters, establishes a provable and verifiable quantum advantage in sample complexity: the number of samples required to solve a problem.
"We stumbled upon the core result of this work by chance while working on a different project," Harry Buhrman, co-author of the paper, told Phys.org. "We had a set of items and two quantum states: one formed from half of the items, the other formed from the remaining half. Even though the two states are fundamentally distinct, we showed that a quantum computer may find it hard to tell which one it is given. Surprisingly, however, we then realized that transforming one state into the other is always easy, because a simple operation can swap between them."
"We stumbled upon the core result of this work by chance while working on a different project," Harry Buhrman, co-author of the paper, told Phys.org. "We had a set of items and two quantum states: one formed from half of the items, the other formed from the remaining half. Even though the two states are fundamentally distinct, we showed that a quantum computer may find it hard to tell which one it is given. Surprisingly, however, we then realized that transforming one state into the other is always easy, because a simple operation can swap between them."
For us dumbnuts (Score:5, Insightful)
Imagine a big box of numbered balls. Someone secretly chooses half of them, that’s set S. You are only allowed to pull balls from S. Your job is to give back one ball that is NOT in S.
Classical world: every time you pull a ball, you just see one number. If the box is big, you have to pull a lot of balls before you’re confident which numbers are missing. Basically, you keep a list of what you’ve seen and guess something not on the list. You might need tons of samples.
Quantum world: instead of one ball at a time, you get a magic “wave ball” that contains all of S at once, like all its numbers are smeared together in a superposition. With some clever quantum tricks, you can flip that wave so it now represents “everything that is not S.” Then you measure it and boom, you get a number from outside S.
So the shocker is this: one quantum sample versus lots and lots of classical samples.
They also argue this isn’t just a weird edge case. Under normal crypto assumptions, classical computers really can’t fake this efficiently.
Important detail: if you convert the quantum thing into ordinary classical samples first, the magic disappears. The power comes from keeping the “wave” intact.
So the paper is basically saying, look, quantum computers are not just faster calculators, they sometimes need far less data to do a job. That’s the whole punchline.
Re: (Score:3)
good if true...
I get so tired of quantum entanglement being a thing that we should all understand... we don't and never will
Re: For us dumbnuts (Score:4, Insightful)
Re: (Score:2)
This seems like nonsense. I think observation is nothing to do with observation but more "making a measurement" It is nothing to do with you looking at stuff.
I don't really get it though. Where does something stop being quantum and start being measured/observed? Is it one electron? Two? Infinite?
Re: (Score:3)
There's just no good reason why observation would be what changes anything. That would only be true in a simulation, whether it's in a computer and mediated by software or in our collective imaginations and transmitted via the celestial aether or some other third even more fantastical thing. It's interference which "does" whatever is actually happening, assuming classical physics makes sense.
ObDisclaimer: I am not married to any theory of existence since I don't actually much care which is true unless there
Re: (Score:2)
Simply put it is impossible to observe anything without interaction.
Agreed, that has always been my understanding of that property of QM, and this is how it was presented to me initially, but since then that seems to be ignored or glossed over by most people talking about it. It's the interaction, not the bare fact of observation.
TBF even that is spooky though when you are sufficiently removed from the thing.
Re: (Score:2)
Observation requires "making a measurement". You can't observe something without measuring it.
OTOH, "making a measurement" doesn't require that YOU interact with the measurement...so the state doesn't have to collapse, just to get spread out. (Every interaction is "making a measurement", even if it's only an electron interacting with a proton, and you never look.) But the state doesn't collapse until YOU joint the interaction, and become yourself entangled.
At the macro level there's so much entangled tha
Re: (Score:2)
You said : But the state doesn't collapse until YOU join the interaction, and become yourself entangled.
This is untrue, as far as I know.
Re: (Score:2)
Check out "Wigner's friend".
Re: For us dumbnuts (Score:2)
Re: (Score:2)
The GP used "observe" but it's entirely unnecessary.
The reason the world doesn't do any of the "weird" quantum stuff IS that it's massively entangled. We can only get the weird stuff by setting up very delicate, very special cases. Then, when we "observe" them, i.e. entangle them with a giant measurement device of some kind that is itself massively entangled with the rest of the universe, the special delicate state "collapses" into an ordinary massively entnagled one.
So surprising.
Re: (Score:2)
Recent result from Penrose showed that a gravitational gradient also collapsed wave functions. So it's not just you. The universe is doing it too.
Re: (Score:2)
Re: (Score:2)
So Stevie Wonder knows quantum? I wonder* if he can rewrite "Superstition" into "Superposition"? Maybe it started out that way, but he realized he had to dumb it down for us Newtonian muggles.
* Pun perhaps intended, but telling you for sure would kill Stevie's cat.
Re: (Score:1)
Addendum: I asked a bot to draft up lyrics for "Superposition". It doesn't fully rhyme, but a decent starting draft. AI sucks at a lot of things, but giving multiple rough-drafts is right up its alley.
(Verse 1)
Very superposition
Particleâ(TM)s about to fall
Thirteen-minute decoherence
Broke the wave function wall
Seven years of bad data
The good state in your past
When you believe in things
That you can't observe, you're gonna break the mask
(Ooh, you're in a superposition)
(Chorus)
Superposition, quantum theory
Re: (Score:1)
Addendum 2: I fixed the stupid Unicode hiccups.
(Verse 1)
Very superposition
Particle's about to fall
Thirteen-minute decoherence
Broke the wave function wall
Seven years of bad data
The good state in your past
When you believe in things
That you can't observe, you're gonna break the mask
(Ooh, you're in a superposition)
(Chorus)
Superposition, quantum theory
If it's split, you'll get weary
When you're here and there at once
Everything is in a state
Superposition, Schrodinger's cat
Alive and dead, imagine that
When you belie
Re: (Score:2)
The OMG quantum is weird crowd like to talk about entanglement as if it's some strange situation. Rather, massive entanglement is the norm. The strange situation is when some monkeys with lasers come along and very carefully disentangle a couple of electrons or whatever from everything else in the universe then let them just barely become entangled with each other.
Per: Relating to quantum is futile (Score:2)
I wonder if a video game can be devised where one has to think in quantum concepts to win. After playing a while quantum rules start to feel natural.
You wouldn't have to try to understand it, trial and error would naturally "teach" it to you. That's how toddlers learn about everyday physics: by playing with it and getting bruised by it. (In this case bruises are merely lost points.)
"Quantum Odyssey" allegedly tries that. Anybody kicked its tires?
Re: For us dumbnuts (Score:2)
Re: (Score:1)
Hologram-esque?
Re: (Score:2)
Sort of. The secret someone in your example goes to a bunch of effort to make the one ball not in S a green one while all the other balls are red. You're colour blind so you have to sample the balls as you say. The QC is not color blind, and has been told in advance it's looking for the green one, so it can just grab it. Except it gets it wrong most of the time so you actually have to do some sampling anyway.
No,
Researchers (Score:1)
Are in universities. These dummies are marketers.
Re:Researchers (Score:4, Informative)
Re: Researchers (Score:2)
Most universities are private and little more than marketing enterprises.
Theoretical result? (Score:2)
I looked through the paper. It seems like they haven't run this on a real quantum computer.
The preparation of the state | by the referee is computationally more expensive as it requires the implementation of pseudorandom permutations. As a near-term toy example, one could implement permutations using the Simplified Advanced Encryption Standard (S-AES) protocol. S-AES uses a block size of 16 bits (as opposed to 128 bits for AES) and a key size of 16 bits as well (128, 192 or 256 for AES). A system size of 16 can display features of quantum advantage: from Theorem 1 with, e.g., =216, =215 and =1/6, any classical algorithm solving complement sampling requires 214 =16384 distinct samples. A quantum circuit implementation of S-AES based on [45] requires only 48 qubits, 168 Toffoli gates, 364 controlled not gates, and 75 not gates.
Why didn't they take the next step and run their algorithm?
Re: Theoretical result? (Score:3)
If you think of every published paper as a grant application for the next round of research, then this would not seem strange.
Re: (Score:2)
Nice tie! (Score:2)
Such a shame there is no hardware to run it on (Score:2)
The QC nonsense needs to die.
Re: (Score:2)
Re: (Score:2)
Only that this is not "budding technology" at all. It is decades old tech that cannot scale. For example, the current actual (!) factorization record on a QC is apparently 28. And that is with a specific algorithm for 28, not a general algorithm for 5 bit.
Not that impressive, isn't it? But there is a lot of misdirection and false claims around.