Quantum Computing and the Limits of the Efficiently Computable - 2011 Buhl Lecture

[@jeffshubert]

Complexity theory bored me in school, but I could listen to this guy all day. Very interesting and entertaining!

[@quelorepario]

This guy is thousand times better explaining extremely advanced concepts than most math professors in the world. Even with his awkwardness @ public speaking, he makes it really enjoyable and simple to follow. If any of you didn't get it, go back to your textbooks, pay attention in class, and finish school.

[@carl14706]

love how giddy he gets when he talks about P and NP. really shows his enthusiasm for the field

[@edgarsanes9107]

This is an amazing lecture, he really is good at lecturing.

[@ACogloc]

@55t1 What Aaronson is saying is that your exponential run time task is not done in linear time because of a sort of massively parallel calculation, but because of the essence of the quantum computer: you shoot the electrons just once and get ONE task done, not many tasks simultaneously. Think about a computer automatically counting in the base of the size of your input. You don't have to try many solutions (e.g SAT values combinations), all of them are checked in one calculation.

[@Gauss156]

This guy is both brilliant and hilarious. Interesting stuff

[@unvergebeneid]

Look up quantum teleportation on Wikipedia: "it does not immediately transmit classical information, and therefore cannot be used for communication at superluminal (faster than light) speed." What you do is to generate two identical random one-time pads and use this to encrypt information that you then send at light speed. You cannot alter the qubit at will and have the same happening to the remote partner as the article implies.

[@atikare]

love the remark 'quantum mechanics is unbelievably simple once you take the physics out'

[@Fransamsterdam]

Is it correct what he tells at 38:40, that you can have positive and negative amplitudes who cancel each other out? I thought the probability was always the square of the absolute value of some amplitude(s), and therefore always not negative. Ofcourse the probability can be zero, if there is destructive interference, but that's part of the computation, in my opinion. I mean, once you calculated the probability is 0.3 for instance, you don't need to calculate again to check if the answer could also be -0.3. Or am I wrong?

[@hujason4944]

a quantum state as a linear operator is just a trace-1 positive semidefinite matrix, which can be processed by any linear operations, including subtraction.

[@ElectricQualia]

This lecture is A okay, okay? Jokes aside brilliant researcher , i learned alot from this talk. Thanks Scott

[@RandallLeeReetz]

I am more interested in the idea that all P problems are actually NP problems… and only appear to be P because we are not calculating the whole of the computation that has occurred since the big bang.

[@MrPerfectlogic]

Here it is; scientist in Australia changed the quantum state of an entangled electron, dedicated equipment in a space craft 1,000,000 kilometers away, detect the quantum change of their entangled electron instantaneously ("spooky action at a distance"). The change in the quantum state of the electron is information. Expand; use multiple entangled electrons and build a binary system (0 and 1 - spin up or down).

[@liuton2005]

Basically he explains that the problem with quantum computers is not the fact that the computer is unable to compute the answer but the problem is to actually read the answer which can be very very close to the other wrong answers. There's always an error in reading measurements and that applies to quantum physics too.

[@rgaleny]

The Seiner tree, does it have applications in comprehending quanta and strings and membranes and such ?

[@unvergebeneid]

No, what you can do is *measure* the spin and the entangled electron sets its spin accordingly. What you can't do is change the spin at will and the other flips around as if by magic. And since you can't set the state, you can't transmit information. You also can't use the timing because there's no way at the other end to know when a measurement has taken place.

[@Muldoonite]

This guy is great.

[@bradleysnay2223]

Really enjoyed this!

[@yp06407012]

Scott Aaronson starts at 4:30

[@teooo]

Write a number as a product of other numbers (factors). Any integer can be written as a product of prime numbers, it's just a hard problem to find them.

[@MrPerfectlogic]

Wrong answer. I tried to include the web link but you tube doesn't allows that. But you can Google for "New quantum teleportation record paves the way towards a worldwide quantum network"

[@unvergebeneid]

While übercomputers would be nice, right now I'd be happy if there was some open source software that does a better job at solving and simplifying equations than sage/maxima.

[@aqwertgbvcxz]

How long is a piece of rope?

[@hats-k2z]

interesting... wish i knew what you were talking about though

[@unvergebeneid]

43:00 Well, of course the assumption that factoring numbers is not in P is also an assumption so it's not clear by that that BQP is really larger than P.

[@feastures]

The problem of people not understanding QC, is that nobody clearly explains what it is.

[@hankh825]

very good!

[@Fransamsterdam]

Very interesting, by the way.

[@Blankname101]

This was interesting.

[@93MickyD2]

Why do all these videos involve TWO people introducing the only person we really want to hear from?

[@RandallLeeReetz]

Exactly. If you have all answers, the problem is filtering out all of the wrong answers. And isn't that what problem solving is… making quantum computing just an instance of computation. Nothing special. Just different.

[@ncoloss1972]

Presumably a quantum computer could simulate the entire universe without requiring the energy of an entire universe. Or more specifically, it only needs to compute the observed universe since that seems to be how nature works anyway. I am thinking Copenhagen interpretation. As such anything in nature is presumably computable.

[@0ldPlayer]

ums: over 9000!!!!!!! awesome lecture, thoroughly enjoyed

[@atikare]

actually starts on quantum computers around 30 min marks, before that its NP probs

[@jdotpenneyatcomputer]

ok, so maybe he's nervous. but I really wanted to know about this stuff and it was SO PAINFUL!

[@jdotpenneyatcomputer]

wow. I could barely listen to this. such valuable information, but nearly non-digestible.

[@paddyxg2]

Quantum computing section starts at 30 mins.

[@adinivermekistemeyengizley6396]

next is me!

[@SterileNeutrino]

2 persons though Charles Stross novels were for real. On-paper version? Google for "NP-complete Problems and Physical Reality"

[@aqwertgbvcxz]

I think pn and p will work great for evolution theory.

[@fabriziodutto7508]

Can we say that we live inside a quantum computer simulation and so, as it happens inside any actual computer's simulation, we can not reach the full power of the computer we're a simulation in, beacuse our simulation uses memory and energy to be computed? This could also explain why nature seems to find a solution to those hard problems, if we can think of a problem, it has to be programmed by someone inside our simulation... :-)

[@xponen]

Very Interesting. I found this to be similar to Einstein's relativity; it prevent object from crossing the speed of C but without the observer noticing it. I believe it's also due to limitation in our "simulation", and if we learn all the technique that "nature" use to hide it, we might be able to use it to make our own perfect simulation... :-)

[@BADSYNE]

assuming the ship/engine has to be exponentially large or that there would even be the necessity of a gas tank is foolish. (57, 58:00)

[@MrPerfectlogic]

0:07:33 - wrong statement, it has been proven time and time again, that information can travel much faster than the speed of light using entanglement principles. Impossible is a state of mind!, nothing is impossible, we just haven’t figured out how to make it possible. It’s called the possibility of the impossible.

[@cculb1]

OKAY MAN! OKAY!

[@jolgiiis]

17:40 most awkward drink ever.

[@oybeutu]

I know it's petty but i keep anticipating him saying "ok".

[@voidisyinyangvoidisyinyang885]

Westerners think repetition is inherently boring. Kind of funny actually. It's very possible repetition is an illusion.

[@naterojas9272]

it seams as if there could be some optimal state using all these "super" methods he mentions towards the end. not practical still but an interesting idea

[@WarzSchoolchild]

0:05:31 Hahahahaha! I am a Carnegie! and Andrew Carnegie's favourite perpetual motion wheel was the famous 8th Century Indian Astronomer Mathematician's "Bamboo Multi-Swastika Quicksilver Wheel" . Tubes of bamboo half filled with Hg. You will never see it, if you never build it! "NULLIUS IN VERBA" ... Why waste words, when proof is in the empirical factual demonstration! The Duke of Devonshire later bought Johann Bessler's adaption of Bhaskara's wheel to drive Chatsworth House's Water Cascade.

[@Zytaco]

I combined a zeno and relativity computer and when I came back it was stolen :/

[@rx327prime]

actually , there are perpetual motion devices existing, sorry.

[@MACAVELLE50]

Every time he said OK I did a shot...Suddenly everything became clear.

[@MinNyeAccount]

@MarthamadaySaamanu new to me!

[@unvergebeneid]

Describe to me a FTL way to communicate using quantum entanglement.

[@aqwertgbvcxz]

It is like asking a question like " How long is a piece of rope? ". Oh..... Geee... Well....... Ummmmm.....mmmmmmm.. ummmmmmmm 2 meters? Oh wait, may be it is 4 meters! Wait wait, may be it is a million billion gazillion meters. ummmmmm.... gee that is a really really hard question. Ok, lets give a million dollars to the person who can generalize a way to this question. As you can see, there is no solution to that unless you already know the answer to it.

[@WarzSchoolchild]

Correction "The Law of Thermodynamics violates Empirical Evidence!" and BTW you have to 'load' a Bhaskara Bamboo Tube Multiple Swastika Wheel, or it degenerates into a chaos wheel/pendulum. Every engineer who sees the design, automatically knows how it works, before the wheel is set in motion. Lagrangian Mechanics urgently needs restriction. NULLIUS IN VERBA Motto of The Royal Society. and ordinary water works fine! or BB shot in jumbo straws etc. Build it, and know! don't argue from ignorance!

[@greg2spook]

speed of light? maximum entropy? absolute zero?......these are just walls to our box....and we don't even know their relationship to one another

[@salzahrah]

I respect this man's knowledge in the field, but it's damn annoying when someone says "uhhh ahhh uhhh" every 5 seconds.

[@MrPerfectlogic]

I gave up at 00:40:27

[@PhiloAmericana]

NKAY!

[@nsareen3457]

P≠NP

[@petrmej]

he must be related to Mr. Mackey :-P

[@MatrixMonitor]

You're on youtube. Please build your empirical factual elsewhat Bamboo machine, make a video and post. Would be enough.

[@adinivermekistemeyengizley6396]

i still fight? not sure how it is going to end? oh my..........offf!

[@jdotpenneyatcomputer]

ok, can't handle it, I'm bailing

[@Rauno315]

1 persons head exploded.

[@jolgiiis]

This guy uses NKAY! as commas and dots.

[@ginocochuyt]

mmkay Mr mackey

[@spechtbert]

ahhh uhh ahhh uhh, i think he came like 100 times in a row.

[@baggybag1987]

you must eat as many calories as stupid pills

[@Israel5535]

Images on my site r true and correct of an event with 2 other witnesses and none others r in existence that I know. How many priests or pastors can tell u that they talk to GOD and yet have no proof or even a witness? As in Ezekiel 13:7 the LORD says that prophets say, "'The LORD says,' But I(GOD) have not spoken," so it is today. Demon is a mistranslation and comes from the Greek word meaning genius or knowledge, a living human being, not a spirit. The LORD comes with trillions of saints.

[@RoyManter]

stop that, monster!

[@then33k4]

after 10 minutes i couldn't stand him anymore. Okay

[@DELEX0GODLESS]

...OK

[@xpscalgary]

easy: P = NP² Million dollars please ;)

[@Israel5535]

With trillions of stars in the heaven's it is the height of ignorance to beleive that man and demons r the most intelligent beings in existence. MYSTERY BABYLON U.S.A. shall be utterly destroyed and cannibalism shall be their daily menu. Isaiah 49:26 “I will make your oppressors eat their own flesh; they will be drunk on their own blood, as with wine. Then all mankind will know that I, the LORD, am your Savior, your Redeemer, the Mighty One of Jacob."

[@bustybossoms]

okay, ummkay, okay, mmkay

[@crhea]

This guy is very interesting to listen to, but he was making me jittery the whole time. SLOWWWW DOWWWWNNNNN!

[@p0wer5000]

i no understand xD i watched the whole thing but owell guess im just not smart enough

[@adinivermekistemeyengizley6396]

abs('not ok');

[@nextblain]

ok......

[@Paumonsu]

mmmmm...okay

[@Ghost-ri7bg]

Uju Anya needs nothing less than being fired from her job at Carnegie Mellon Uni for such foul openly made hate indicator. For a place of Academia & thus Learning she is not of sound mind to be holding even the job of janitor's assistant..

[@NavjotGraphicDesign]

okay?

[@neonDog]

Mmmmkay

[@SRacingUpTune]

ok?

[@atomichurley]

uhh

[@purplewizard]

If you laughed at these jokes you are a true nerd.

[@PacRimJim]

I bet he doesn't even know who Justin Bieber is. So there!

[@filmfredrik]

Watching this makes one realize just how unbelievably brilliant some people like Sam Harris, Richard Dawkins, Neil DeGrasse Tyson and Sam Harris are at communicating their scientific ideas...

[@MarthamadaySaamanu]

Talk is nice, but the jokes are old :)