Quantum contextuality
Recently, quantum contextuality has been explored as a potential tool for quantum computing. In 2013, Robert Raussendorf showed that in general, any Mermin-like, inequality-free proof for quantum contextuality (such as the Kochen-Specker theorem) can be turned into a measurement-based quantum computation. More formally, "under quite natural assumptions for multi-qubit systems, MBQCs (measurement based quantum computations) which compute a non-linear Boolean function with sufficiently high success probability are contextual." Then in 2014, Mark Howard, et. al. showed that applying contextuality to magic state distillation (MSD) provides a means for arriving at universal, fault-tolerant quantum computing. MSD is a process by which a single qubit's polarization is increased along one of several "magic" directions and its state is considered "magic" once its polarization reaches a certain level. In particular, the group proved that states are non-contextual if and only if they cannot be used as inputs for magic state distillation. This provides a selection criteria for proper input states needed in MSD, and by extension aids in the efficient creation of magic states that, when coupled with fault-tolerant operators, allows for universal quantum computing. In both cases, contextuality has a potential advantage over other quantum computational techniques since contextuality itself can be thought of as a theory of information that is built directly into quantum mechanics. Comparatively, more traditional quantum phenomena such as entanglement and interference use delicate physical states which are incredibly susceptible to noise and very difficult to manipulate experimentally.
Quantum computing
Besides factorization and discrete logarithms, quantum algorithms offering a more than polynomial speedup over the best known classical algorithm have been found for several problems, including the simulation of quantum physical processes from chemistry and solid state physics, the approximation of Jones polynomials, and solving Pell's equation. No mathematical proof has been found that shows that an equally fast classical algorithm cannot be discovered, although this is considered unlikely. For some problems, quantum computers offer a polynomial speedup. The most well-known example of this is "quantum database search", which can be solved by Grover's algorithm using quadratically fewer queries to the database than that are required by classical algorithms. In this case, the advantage is not only provable but also optimal, it has been shown that Grover's algorithm gives the maximal possible probability of finding the desired element for any number of oracle lookups. Several other examples of provable quantum speedups for query problems have subsequently been discovered, such as for finding collisions in two-to-one functions and evaluating NAND trees.