191–200 of 210 posts
Earlier quoted context omitted.
Looking forward to when leetcode problems require BPQ complexity analysis
We might never retire but at least we’ll grind out leetcode in our 60’s while on adderall, ozempic, lions mane etc…and won’t feel a day over 55!
Earlier quoted context omitted.
> I have heard this mentioned several times in the last decade or so : "The only thing a quantum computer definitively does better than a classical computer is simulating a quantum computer." And, hopefully, other quantum systems in general! I can see that helping with material science. That can have huge multiplier effects on the rest of the economy. But I agree with you, that other serious applications of quantum c…
I thought one of the main advantages of QC was that it could (theoretically) solve existing problems that have exponential time complexity with more efficiency. Isn’t the idea that it could make everything faster? Or did I fall for the marketing.
Earlier quoted context omitted.
> Isn’t the idea that it could make everything faster? If that is your understanding, then yes, you have unfortunately fallen for the very mistaken reporting on this. There are specific algorithms that Quantum Computing can solve faster than regular computers. Some of these algorithms are incredibly important, and a faster solution to them would cause serious changes to the world, namely Shor's algorithm, which would…
Huh yeah I guess I need to learn more. My layman’s assumption was that it would help with a lot of NP problems that involved recursion or backtracking algorithm would benefit from it. From some quick googling it seems like they have already designed QC algorithms for traveling salesman etc. Isn’t that sort of meaningful or am I missing something? I could totally see the argument that they are physically impractical a…
Recursion is more of a property of how you write your algorithm, than of the problem.
Eg Scheme or Haskell as languages have no built-in facilities for iteration, no for-loops, no while-loops; the only thing you get is function calls. (Well, that and exceptions etc.)
However you can built for-loops as libraries in both Scheme and Haskell. But they will be built on top of recursion.
To make matters even more interesting: once you compile to native code, all the recursion (and also all the for-loops and other fancy 'structured programming' constructs) go away, and you are back to jumps and branches as assembly instructions.
None of this changes whether a given class of problems is in P or NP or (almost!) any other complexity class. Just like getting a faster computer doesn't (usually!) change the complexity class of your problems.
> I could totally see the argument that they are physically impractical and therefore not likely to be actually used vs parallelizing conventional computers.
Quantum computers are impractical now. But as far as we can tell, that's "just" an engineering problem.
In the long run one of two things will happen:
- Either engineering improves and we will be able to build good quantum computers (though perhaps still not better than classical computers for the same amount of effort) - Or, we discover new principles of quantum mechanics.
Basically, quantum mechanics is one of our most successful physical theories, if not the most successful theory. And as far as we understand it, it allows quantum computers to be built.
So either we will eventually manage to built them, or (more excitingly!) that's not possible, and we will discover new physics that explains why. We haven't really discovered new physics like that in a while.
Earlier quoted context omitted.
I thought one of the main advantages of QC was that it could (theoretically) solve existing problems that have exponential time complexity with more efficiency. Isn’t the idea that it could make everything faster? Or did I fall for the marketing.
The basic idea is that for a certain class of problems, you can have the quantum computer skip certain incorrect paths on the calculation by having their probability amplitudes cancel each other out.
The fact this prize exists is admitting that no one has figured out a use for quantum computers. I have heard this mentioned several times in the last decade or so : "The only thing a quantum computer definitively does better than a classical computer is simulating a quantum computer." Whether this capability is useful is up in the air. Note that in practice, classical computers are going to be better at factoring nu…
There have been XPRIZE competitions for vehicle efficiency, oil spill technology, more efficient rockets, health sensors, AI systems, genomics, etc. Whether or not quantum computers have practical applications, the prize itself is not evidence of that.
All of which are based on existing technologies that have been delivering for decades if not an entire century (vehicle efficiency). Even something as nebulous as "AI systems" has been around for twenty years in the form of Google's original semantic search capabilities.
This "Quantum AI" prize, however, is a solution in search of a problem.
Earlier quoted context omitted.
I thought one of the main advantages of QC was that it could (theoretically) solve existing problems that have exponential time complexity with more efficiency. Isn’t the idea that it could make everything faster? Or did I fall for the marketing.
This is true in theory but don’t think it’s ever been proven in practice
Earlier quoted context omitted.
If a problem can be reduced to efficiently sampling from the summation of an exponentially large number of FFT's, then a quantum computer will destroy a classical computer. If a task can't be efficiently reduced to such a problem, then a QC probably won't ever help at all; the square root time advantage from grover's algorithm is too easily overwhelmed by simple engineering factors.
What's stopping classical computers from doing this sampling? If it's sampling, you don't have to deal with the exponential here.
“We give new evidence that quantum computers—moreover, rudimentary quantum computers built entirely out of linear-optical elements—cannot be efficiently simulated by classical comput- ers. In particular, we define a model of computation in which identical photons are generated, sent through a linear-optical network, then nonadaptively measured to count the number of photons in each mode. This model is not known or believed to be universal for quantum com- putation, and indeed, we discuss the prospects for realizing the model using current technology. On the other hand, we prove that the model is able to solve sampling problems and search problems that are classically intractable under plausible assumptions.”
Which is the basis for the experiment discussed here: https://scottaaronson.blog/?p=5122
Earlier quoted context omitted.
I thought one of the main advantages of QC was that it could (theoretically) solve existing problems that have exponential time complexity with more efficiency. Isn’t the idea that it could make everything faster? Or did I fall for the marketing.
You got a useful response already, so let me give you a good response: https://www.smbc-comics.com/comic/the-talk-3
Earlier quoted context omitted.
Thanks for reaffirming Poe's law. I was amused by how 'cell phone' was taken as a given, when talking about a CCD sensor.
No, it was not taken as a given, it was an example of a very common product that digital image sensors enabled. I could have chosen e.g. digital cinema cameras, but they would not nearly have the same profound effect as cell phone cameras have had on society.