This work package will develop quantum algorithms for tasks which occur in “big data” applications: those where the quantities of data produced are so large that traditional data processing methods are inadequate. We have identified several specific directions where there is good preliminary evidence that quantum algorithms could substantially outperform classical computing. Each models a practically relevant task in sufficient generality to enable quantum speedups that are applicable across many different problems. These are sketching, property testing, and systems of partial differential equations.
Workpackage leader: Ashley Montanaro (University of Bristol)
Significant achievements
- We developed new quantum communication protocols in the “sketching” (simultaneous message passing) model that achieve provable exponential speedups over their classical counterparts for natural problems relating to large data sets. Based on previous work on quantum fingerprinting, we described protocols for efficient approximate computation of Hamming distances between bit-strings, and distances within graphs. This work was published in Physical Review A and highlighted as an Editor’s Suggestion.
- A very natural problem in the context of testing properties of large data sets is determining whether a Boolean function is a junta (i.e. depends on only a small number of variables). In the challenging setting of distribution-free testing, where one does not know in advance under which distribution to measure the distance from satisfying the property, we gave a quantum algorithm that achieved a quadratic advantage over the best classical algorithm then known (while this work was under review, Bshouty developed a classical algorithm achieving a similar complexity).
- In mathematical finance, we developed the first quantum algorithm for the classic problem known as constrained portfolio optimisation: assembling the optimal portfolio of financial assets that maximises the expected return for a given level of risk, under various constraints. The algorithm we develop achieves a polynomial speedup over corresponding classical algorithms. As well as giving theoretical proofs of correctness and complexity, we carried out numerical experiments to estimate the likely level of advantage the quantum algorithm would achieve.