TODO list of Chapter 3

[Scinawa]

This issue is mostly a TODO list for me, for things that I will do in the future, in order to improve Chapter 3.

• Small typos:

  • In "Definition of block encoding from sparse access" in the original paper maybe they have a typo in [2^w]-1 (what is a set minus 1?)
  • In "Definition of block encoding from sparse access": in the original paper there is a comma too much in the asymptotic complexity of the number of qubits.

• From papers:

  • Rewrite more clearly the proof of Appendix A of Recommendation system paper.
  • Write mitigation techniques for "the problem with Grover-Rudolph".
  • Add content on "Working with classical probability distributions" section.
  • Include Memory Compression with Quantum Random-Access Gates
  • Include Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications
  • Include: qram trick from Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints lasso paper of RdW
  • Add content from Lin EXPLICIT QUANTUM CIRCUITS FOR BLOCK ENCODINGS OF CERTAIN SPARSE MATRICES
  • Include Revisiting dequantization and quantum advantage in learning tasks
  • Double sparse quantum state preparation https://arxiv.org/pdf/2108.13527.pdf
  • Encoding patterns for quantum algorithms

• Add discussion on factorization of matrices, in order to shed insight into $\mu(A)$ and $U=W \circ P$ factorizations for the quantum access of a matrices (this is already in the comments)

• In the comments I wrote "For the choice of the data structure that leads to a value of $\mu$ equal to the Frobenius norm of the matrix under consideration, this can be done even on the fly, i.e. while receiving each of the rows of the matrix. For the choice of $\mu$ related to a $p$ norm, the construction of the data structure needs only a few passes over the dataset. ". Can I be more precise than this?

• Mention that even if we work with the symmetrized version of $A$ (Block encodings from quantum data structures) and Definition 3.8, it does not matter too much, as we can always adjust our algorithms to work in this settings.