Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA

news.ycombinator.com

Post reply on HN
Print view View original

181–190 of 373 posts

Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA

#181

Post by mygo »

martin1975 wrote: post #99
ScottAaronson wrote: post #88

Earlier quoted context omitted.

My position on the technical fundamentals never changed much: namely, D-Wave is building devices that could be interesting from various engineering perspectives, but that as far as most of us can tell, are not getting speedups over existing computers that are clearly attributable to quantum computation (as opposed to building special-purpose hardware that's, essentially, very fast at simulating itself). If you want q…

Am I hearing this right, you think the whole multiverse concept is... meta-physics at best?

Despite the scientific method giving rise to the fact-based ever-improving test-able body of work we call Science.. that doesn’t stop people from creating their own religions and beliefs based on it.

Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA

#182

Post by danbruc »

ScottAaronson wrote: post #159
schoen wrote: post #70

Earlier quoted context omitted.

(Not Scott!) The Halting Problem's unsolvability is proven in a fully abstract mathematical way, and so the truth of this result is as logically necessary as the truth of other mathematical theorems. It doesn't refer to anything about physics. So it seems like this question might be better bifurcated into Why do we live in a world in which Turing machines are a good model for what computations we can physically perfo…

Yup. :-) Or better yet, we could bifurcate into: (1) Why is our universe apparently unable to solve the halting problem for Turing machines ? The answer, presumably, is a combination of the physical Church-Turing Thesis (specifically, the apparent impossibility of Turing-uncomputable processes in our world), with Church and Turing and Post's theorem on the unsolvability of the halting problem. Of course one could the…

Once you have those properties, the inability of any given computational model (even a super-Turing model) to solve its own halting problem is just a matter of logic, as schoen said.

This seems to assume that logic provides some form of undeniable truth but I am not sure that this is the case. Sure, every system of logic is hopefully consistent and you can use it to derive true statements within it by simply playing a game of symbol manipulation, and in that sense the system is a source of undeniable truth. But when we are using logic to reason about the real world, we need the real world and the logic we use to be compatible. Classical logic works great in the classical world but quantum mechanics seems to push it to its limits. You can certainly still use it if you are careful, but it seems no longer a really good fit once you no longer have your particles either here or there, either spin up or spin down.

So logic seems much more like physics if you want to apply it to the real world instead of just using it for the fun of symbol manipulation. There are systems of logic that are useful to describe the world and there are ones that are less useful or probably even ones yielding wrong conclusions about the real world. Long story short, I am not sure that we can conclude that there will be halting problems for super-Turing machines because we can not be sure what kind of logic would be adequate to describe those machines. Not that I consider this a likely scenario or whatever, I just think we have to be more careful when saying something is just a matter of logic.

Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA

#183

Post by jey »

EtherTyper wrote: post #156

Will non-linear quantum computers ever be possible? If so, how would they be made, and what would programming them be like? Do we still model non-linear states with vectors and transformations with unitary matrices?

What does "linear" mean to you? Integration is linear[1]. The Hilbert space of all the functions you care about is linear[2]. Life is locally linear[3]. So maybe "non-linear" is just a red herring.

1. https://en.wikipedia.org/wiki/Linearity_of_integration

2. Not really but close enough.

3. I don't know what I mean either, but https://en.wikipedia.org/wiki/Linear_time-invariant_theory is interesting anyway.

Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA

#184

Post by FartyMcFarter »

enriquto wrote: post #106
svat wrote: post #91

Earlier quoted context omitted.

He's already covered that; not sure what's left to explain: he's said that if P=NP and if we get there with a practical running time algorithm (e.g. one that solves 3SAT in O(n^4) or something, and with reasonable constants too), then such-and-such consequences. So what are you asking?

The second part of the claim seems much, much stronger than the first part, but he makes it sound like it's a minor detail. I am confused as to why.

I believe section 1.2.1 of Scott's P ?= NP survey addresses your question:

https://www.scottaaronson.com/papers/pnp.pdf

Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA

#185

Post by ahelwer »

Hey, Scott! Love your book, Quantum Computing Since Democritus. There is one section which confused me, in the Quantum chapter (https://www.scottaaronson.com/democritus/lec9.html). I have two questions:

1) You say applying the unitary operation is the quantum analogue of "taking a coin and flipping it" - what do you mean by this? Could we think of, for example, a pair of slits as applying this transformation on a photon qbit being sent through them, so it's now in superposition with regard to which slit it went through?

2) What does it mean when you say there are two paths to |1>? I understand this section is getting at the physical underpinnings of this mathematical model, but I can't quite wrap my head around how there are two "paths". My mind is stuck thinking of the Bloch sphere as a state machine you can deterministically hop around by applying unitary transformations.

P.S. I did a talk called Quantum Computing for Computer Science which covers everything up to the one-bit Deutsch Oracle problem in 1.5 hours; I found that presenting quantum algorithms as running on a "unit circle state machine" (basically 2d Bloch sphere by restricting states to real numbers) was a very effective way to explain the subject to software engineers! (https://www.youtube.com/watch?v=F_Riqjdh2oM)

Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA

#186

Post by 781 »

opportune wrote: post #164
jovial_cavalier wrote: post #109

Earlier quoted context omitted.

I would also like to know the answer to this. Popular culture has seemingly latched onto the phrase "quantum computer" and decided it's the next logical step for computing in general, without ever really defining what it is or thinking about it too clearly.

Well, never is a long time. I guess the more interesting question (to me) is whether engineering challenges will be easily overcome so as to make quantum computer components cheap and ubiquitous, or if there's some innate difficulty to their production that will make them uncommon for everyday personal use.

People struggled for 40 years to make a blue LED.

Even if quantum computers required near zero temperatures, superconductors and such stuff, there is no reason why you couldn't have all that in a no-serviceable-parts-inside box if the economic incentives were strong enough.

Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA

#187

Post by jkabrg »

JakeTyo wrote: post #118

Why don't we call Qbits just "qits". Since Quantum-Binary-Digit doesn't really make sense. Do people in the field refer to them in other ways?

A qubit is a linear combination of |0> and |1>, and a qutrit is a linear combination of |0>, |1> and |2>. I remember Scott Aaronson once suggested building QCs with qudits (or qu-n-its with n>2).

Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA

#188

Post by FartyMcFarter »

MrXOR wrote: post #92

Hi Scott, What is the current status of PvsNP problem? P=NP or P!=NP? Is any relationship between PvsNP problem and Riemann Hypothesis? Who to follow to know the progress of solving PvNP problem?

https://www.scottaaronson.com/papers/pnp.pdf

Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA

#189

Post by ahelwer »

ScottAaronson wrote: post #140
DC-3 wrote: post #3

Hi Scott, 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 syn…

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 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!

Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA

#190

Post by stcredzero »

ScottAaronson wrote: post #140
DC-3 wrote: post #3

Hi Scott, 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 syn…

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…

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.

Post reply on HN