171–180 of 373 posts
I take it you don't believe in the SIA? Is this paradox irreducible? Is the world going to end soon?
If I use a quantum random number to pick my actions does that mean there's a universe where I took each option? This terrifies me
Also, what do you find terrifying about the existence of multiple universes where every possible outcome of a decision you make plays out?
What would be your advice for older (25+) people who want to get into science? Is it even possible? Or should I just accept that the train has left and focus on something else? Can you develop your math/logic/critical thinking skills at that point? How about if you never excelled at these topics in school? Is hard work enough, or do you think some people are born with these talents?
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…
> This is partly because, even assuming you accept the Many-Worlds Interpretation, "your" moral concern and responsibility presumably extend only to those branches that are in "your" future -- you have no contact with the other branches! Would you say that the only moral way to implement quantum suicide is with a Doomsday Device that would destroy the entire world, thus ensuring your actions won't affect anybody else…
As 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…
Check out some lecture notes, e.g. https://cs.uwaterloo.ca/~watrous/LectureNotes/CPSC519.Winter...
What good is oracle separation? The recent separation between BQP and PH, for example, doesn't seem to mean much. Of course such results may spur the discovery of new proof techniques, or new ways of thinking about a problem, but is the result itself useful? I must be missing something, like a way of stringing together oracle separations to produce a real separation... or is it just the case that oracle separations a…
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.
Here's a (very slightly) more rigorous justification:
If P=NP, then any NP problem is in P with at most a polynomial slowdown. That is, if there's an algorithm taking T steps on a non-deterministic Turing machine, we can solve it on a deterministic Turing machine in f(T) steps, where f is a polynomial. Presumably, a "practical" algorithm would be one for which f has a low degree.
The kinds of algorithms we're concerned about in cryptography (and plenty of other fields) already have low time complexity. For example, generating or verifying an HMAC is O(n) in the length of the input. So if we had a way to solve NP problems with a low-degree polynomial slowdown, we could break HMACs in low-degree polynomial time.
It doesn't matter that there are O(n^1000) problems out there that would still be realistically unsolvable, because those problems don't have practical applications in the first place.
Earlier quoted context omitted.
You're assuming it's possible without explicitly saying it?
If it's not possible, then the answer is clearly 0. If it is possible but not practical for solving any problems, that's a thing one would want to know. If it's possible but unlikely to be practical within the next ten years, that's even more useful. Perhaps it's possible and already practical for some problem. I don't know what that is, so it would be good information. In all of these cases, it's Scott's presumably…