Hello Scott, can encrypted data on blockchains easily be decrypted with quantum computers in the coming decade?
No, almost certainly not in the coming decade. See my answer here: https://news.ycombinator.com/item?id=17429547
I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA
291–300 of 373 posts
Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA
#292Hi 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
+1
There's no clear relationship between P vs. NP and the Riemann hypothesis, except that the generalized Riemann hypothesis (GRH) would let you derandomize certain randomized algorithms, and also Mulmuley's Geometric Complexity Theory (a speculative approach to P vs. NP using algebraic geometry and representation theory) involves some of the same mathematical objects that were used to prove the analogues of RH over finite fields.
Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA
#293Do you ever still do exercises? What's the last thing you learned that other people might have learned as students?
I'm constantly learning new things that to people from other fields would be freshman-level trivialities! The most recent such example would need to be something I learned today. For example, maybe a little tidbit that I picked up from Sanjeev Arora's STOC'2018 tutorial on deep learning (where I was this morning): it turns out, backpropagation is just a dynamic programming algorithm for calculating a gradient in time linear in the size of the network, improving over the quadratic time that one would've needed naively.
I feel bad that I rarely have the time (or willpower!) to do exercises anymore, though I'd probably benefit if I did.
Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA
#294As a programmer and practitioner, I'm curious about what kinds of skills and training it takes to program quantum computers. Can you shed some insight into what's really different about the tools and task of programming a quantum computer versus using classical programming languages and tools? Do you think quantum computer programming will rapidly become standard training for CS undergrads, or do you expect it to rem…
Thanks!!
I imagine that programming QCs will be a lot like programming classical computers, except with an additional body of technical knowledge that one needs to master. In that respect, it will be a lot like 3D graphics programming, or crypto programming, or AI programming, or compiler programming. And much like with those other types of specialized programming, even in a world filled with useful QCs, I imagine that only a minority of programmers would really need to understand how to interface with them.
Everyone: OK, I'm going to sleep now, since I need to catch a flight tomorrow morning. I'll try to answer a few more questions on the plane, but then I'll probably call it a day (or rather, two days :-) ). No additional questions please. Thanks for all the interesting questions!
Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA
#295Hi! So, what do you do when you're not flipping qubits around? Got any cool stories you wanna share?
When I'm not flipping qubits around, I eat, sleep, blog, answer emails, play with my two kids, get depressed reading the news about US politics, and then get even more depressed reading people saying mean things about me and my nerdy friends on Twitter and Reddit.
Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA
#296What advice would you give for productivity/getting things done?
I'm like the worst person on earth to be giving anyone else advice about that!! Do you have any idea how much time I waste obsessively reading the news, or worrying about people saying mean things about me on social media, rather than doing research or anything else useful for the world? I suppose my advice would be: don't do what I do. As my former PhD adviser, Umesh Vazirani, likes to tell people, "concentrate on t…
> how much time I waste obsessively reading the news
This is oddly comforting. As Tim Ferris said in Tools of Titans, every successful person is dysfunctional in some way. I guess the trick is to work around your own personal deficiensies, and that's something everyone must figure out on their own.
Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA
#297Is there a model of a computation that stands to quantum computation in the same way a universal Turing machine stands to classical computers, or is the UTM already enough?
Yes, you can define a universal quantum Turing machine, which is a single quantum Turing machine U able to simulate any other quantum Turing machine M (at least, to arbitrary precision) given a coded description of M on its tape. This is one of the main observations David Deutsch made in his famous paper from 1985.
Thanks, and thanks for spending a big chunk of your time here!
Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA
#298Hey there Scott! I just wanted to say I wrote a student-paper on quantum computational complexity last year and I felt like your papers made up almost 90% of my references. Thank you for making my learning about the subject possible! On to my question: I'm working on a capstone project right now that's using quantum computing to create a small video-game. I'm using the 5-qubit quantum experience from IBM and I was wo…
That's a tough one! So far, I've only seen ONE game meant to teach quantum mechanics that I thought actually worked, in terms of being (1) actually about QM rather than some vague analogy, and (2) fun to play. It's this one: http://quantumgame.io/ Notably, this game doesn't even try to teach about entanglement (which, no surprise, is hard to keep track of in your head!). Tt deals only with a single photon passing thr…
That game is really quite cool, and certainly in the same vein as what I was thinking of doing - thanks so much for the suggestion (I've already spent too much time solving puzzles)!
I am looking at using something like the Quantum Experience for two reasons: 1) Because giving people real quantum computing results is really cool, and 2) Because it's my capstone project and the work has to have a certain threshold of technical exploration. That being said, I'm not well-versed in alternatives that could maybe just simulate quantum properties without having to go through an actual quantum computer.
I have been looking into creating a small quantum neural net (with either real or simulated qubits) to show how that differs from a neural network running on classical computing. I've been trying to work that into a game idea but I'd be lying if I said I've come up with anything compelling yet. If you got any cool game mechanics/ideas you think quantum computing resources would lend themselves to then I'm all ears!
Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA
#299Earlier quoted context omitted.
Who said anything about physics? I was thinking about axioms/logic systems and finitism.
> Who said anything about physics? You did. You asked about why the universe we live in has a particular property. That's a question about physics.
Well I obviously don't think so, and all you've done is state the opposite claim.
Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA
#300Earlier quoted context omitted.
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 y…
Do you mean all the possible solutions to a problem when you say 'answer space' ?
That's how I would interpret it, yes