Quantum algorithms conquer a new kind of problem
quantamagazine.org
Quantum algorithms conquer a new kind of problem
1–10 of 35 posts
Re: Quantum algorithms conquer a new kind of problem
#2So, if I understood correctly, the article seems to say 'learning with errors' problems are now found to be efficiently solvable by quantum algorithms.
However, I seem to remember that many NIST post-quantum crypto algorithms are based on variants of LWE problems.
Is this the same sort of LWE problems, or does the new speedup not apply for some other reason?
Re: Quantum algorithms conquer a new kind of problem
#3Will quantum computing destroy blockchain and classical encryption algorithms as we know? So there will be a need for quantum blockchain and quantum encryption.
Re: Quantum algorithms conquer a new kind of problem
#4> researchers invented a fundamentally new kind of problem that a quantum computer should be able to solve exponentially faster
Telling of the status of the field.
Re: Quantum algorithms conquer a new kind of problem
#5> researchers invented a fundamentally new kind of problem that a quantum computer should be able to solve exponentially faster Telling of the status of the field.
I think the idea is that you might be able to reduce other problems to this problem space.
Re: Quantum algorithms conquer a new kind of problem
#6So, if I understood correctly, the article seems to say 'learning with errors' problems are now found to be efficiently solvable by quantum algorithms. However, I seem to remember that many NIST post-quantum crypto algorithms are based on variants of LWE problems. Is this the same sort of LWE problems, or does the new speedup not apply for some other reason?
I think the article is saying that the new class of problem was inspired by LWE, but adds some additional restrictions.
Edit: quotes showing this:
> Problems like this came to be called “learning with errors,” because the shove and the wind act like a source of random error on the original direction. There is evidence that it is hard to solve for both classical and quantum algorithms.
> Yamakawa and Zhandry tweaked the setup. They modified the strength of those starting shoves, making them more predictable. They also caused the wind to be determined by a random oracle so that it was even more random in certain cases but completely dormant in others.
Re: Quantum algorithms conquer a new kind of problem
#7> researchers invented a fundamentally new kind of problem that a quantum computer should be able to solve exponentially faster Telling of the status of the field.
[deleted]
Re: Quantum algorithms conquer a new kind of problem
#8Will quantum computing destroy blockchain and classical encryption algorithms as we know? So there will be a need for quantum blockchain and quantum encryption.
Post-quantum cryptography is a thing:
Re: Quantum algorithms conquer a new kind of problem
#9I'm going to admit, I only skimmed the introduction of the paper, but this quote from the article appears very misleading
> They also caused the wind to be determined by a random oracle so that it was even more random in certain cases but completely dormant in others.
Assuming "random oracle" means what it typically does, that appears to be a pretty poor characterization of what a random oracle does to a problem.
In particular, a (non-random) oracle is a public string O such that both the algorithm and the function one is trying to compute can depend on O. One valid oracle (probably the most famous interesting one) is the halting oracle: the string that at position with index x tells you whether or not the TM with binary encoding ever halts on an empty input. While access to this string would give you an avenue to solving the standard halting problem in finite time (the time taken to do a single lookup), the halting problem relative to this oracle is still uncomputable because you're now additionally tasked with solving the halting problems for machines that also know what O is, and therefore can pull off the same self-simulation trick to fool you as in the standard proof.
An algorithm existing relative to a random oracle means that if each digit of O were sampled from independent fair coin flips, then with probability 1 the algorithm could solve the problem. This is different from the standard definition of randomized complexity classes in that the correct solution to a problem can still directly depend on O itself.
Relative a random oracle, it is an exercise to prove some results of otherwise immense magnitude such as P≠NP, #P≠PSPACE, IP≠PSPACE, and so on. But the problems underlying these separations tend to be contrived, e.g. "does the string O contain a substring from some set A", where A is chosen specifically so that (i) it contains a string in O with an (a priori) 50% chance, (ii) one class information-theoretically cannot identify this string without enumerating beyond its available resource constraints, and (iii) the other class can exploit its added power to easily solve the problem. For example, perhaps a "P algorithm" would need to brute force 2^N positions for such a string, but an "NP algorithm" can nondeterministically guess where in the oracle to look to find it.
Random oracles are great for proving separations, but their applicability to the underlying classes is limited. Concretely, the result I mentioned above of IP≠PSPACE is straight-up wrong in the unrelativized world. The oracle isn't just playing with the randomness involved, it's fundamentally asking which questions one is allowed to ask, and opens an avenue toward posing a whole bunch of "junk" problems that become uninteresting as soon as the pure noise oracle string O is discarded.
In light of this, I'm not sure how to view this result. Is it to be read as Yet Another Random Oracle Separation, or is there something deeper here that I should take away from the result?
Re: Quantum algorithms conquer a new kind of problem
#10I'm going to admit, I only skimmed the introduction of the paper, but this quote from the article appears very misleading > They also caused the wind to be determined by a random oracle so that it was even more random in certain cases but completely dormant in others. Assuming "random oracle" means what it typically does, that appears to be a pretty poor characterization of what a random oracle does to a problem. In…
the article goes on to say
> they then adapted their algorithm to solve a real-world version of the problem, which replaces the oracle with an actual mathematical equation.
which probably negates what you said I think