Projects per year

## Abstract

The

of the input one at a time, and seek to minimise the amount of storage space, or passes over the data, used to approximate

*k*’th frequency moment of a sequence of integers is defined as*F*= ∑_{k}*, where*_{j}n^{k}_{j}*n*is the number of times that j occurs in the sequence. Here we study the quantum complexity of approximately computing the frequency moments in two settings. In the query complexity setting, we wish to minimise the number of queries to the input used to approximate_{j }*F*up to relative error ε. We give quantum algorithms which outperform the best possible classical algorithms up to quadratically. In the multiple-pass streaming setting, we see the elements_{k}of the input one at a time, and seek to minimise the amount of storage space, or passes over the data, used to approximate

*F*. We describe quantum algorithms for_{k}*F*_{0},*F*_{2}and*F*_{∞}in this model which substantially outperform the best possible classical algorithms in certain parameter regimes.Original language | English |
---|---|

Pages (from-to) | 1169-1190 |

Number of pages | 22 |

Journal | Quantum Information and Computation |

Volume | 16 |

Issue number | 13-14 |

Publication status | Published - 1 Oct 2016 |

## Keywords

- Frequency moments
- quantum query complexity
- quantum streaming complexity

## Fingerprint

Dive into the research topics of 'The quantum complexity of approximating the frequency moments'. Together they form a unique fingerprint.## Projects

- 1 Finished