A quantum-inspired classical algorithm for recommendation systems

it's also easy to check that a solution is valid (but we don't know if the opposite is true). This class contains interesting problems such as prime factorization on which all the current Web's security depends. It's easy to check if a factorization is valid, but it's hypothesized that it's hard to actually find it. Now the interesting part is that we're not sure it's actually true, so the security house of cards might actually tumble at some point (if it hasn't already secretly). — BPP contains all the problems that you can solve in polynomial time (so like P) but with a chance of less than 1/3 of being incorrect! In practice, we run the algorithm several times to reduce the probability of being wrong to less than 2^(−ck) (c is a positive constant, k is the number of times it's run). — BQP is probably the most interesting class here. It's just like BPP but on a quantum computer. Now the interesting part is that we don't know (yet) an efficient way of finding the prime factorization on a classical computer. But on a quantum computer, we have the infamous Shor's algorithm which can solve this problem in polynomial time with a bounded error! ————————————————————————————————————————————————————————— The current knowledge about complexity classes is that P ⊆ BPP ⊆ BQP. We don't know how NP and BQP relate to each other. What does this mean? We don't know if quantum computers can solve harder problems theoretically. But they seem to do sometimes in practice to the best of our knowledge. Coming back to the Shor's algorithm example, we don't know any classical algorithm that can solve the prime factorization problem as efficiently. But this doesn't mean that such an algorithm doesn't exist! Now you might think that all of this is only theoretical considerations that only mathematicians care about. After all, we don't care if theoretically there might exist efficient classical algorithms for supposedly hard problems if we don't find them anyway right? This is a valid observation. If big enough quantum computers become a reality one day, we'll be able to solve some hard problems right away. However in the meantime, we might totally find efficient classical algorithms making quantum computers less useful. Actually, it has already happened last year[1]! A recommendation problem that we thought was intractable by classical means (but easy to solve with quantum computers) turned out to be solvable more easily than expected by a classical computer. This classical algorithm draws inspiration from quantum algorithms however. So if anything, quantum computing will force us to look at problems from another perspective and solve them in novel ways. [1] https://arxiv.org/abs/1807.04271

like, this problem is ill-posed. We make this problem tractable through the standard assumption that T is close to a matrix of small rank k (constant or logarithmic in m and n). This reflects the intuition that users tend to fall into a small number of classes based on their preferences. With this assumption, it becomes possible to infer information from subsampled data. We can determine the classes a user lies in, and use information about those classes to give a likely-to-be-good recommendation") The original quantum recommendation algorithm paper involved both a simplifying assumption about the sorts of consumers one was models and a system of sampling to get a good approximation ("The literature on theoretical recommendation systems is fairly scant, because such algorithms quickly run up against the limits of their model, despite them being somewhat far from the results seen in practice.") https://arxiv.org/pdf/1807.04271.pdf