I would like to learn more about quantum algorithmics in next months/years.
I wonder - do I need to be very very good in "classical" algorithmics to be good in quantum algorithmics, or are they almost "independent" and I don't need more than basics or things I will learn "ad-hoc" when I will be needing them?
The same about probability - does quantum algorithmic uses very advanced probability theory, like more than 1 semester course of probability on Math studies? If Yes, does it use only discrete probability or also continuous probability?
Thanks in advance for answers. Stay cool!
Quantum Computing brings in a lot of background information. Linear Algebra, some familiarity with complex variables, and trig are necessary. Everything else can really be picked up in the process of taking the course. A lot of Quantum Computing courses also introduce a lot of the linear algebra (e.g., Hilbert Spaces, inner products, tensor products).
With that said, there are a lot of subjects that will almost certainly contribute to a better understanding. In a one-qubit system, the qubit states correspond precisely to the unit vectors in $\mathbb{C}^{2}$. These unit vectors sit on the surface of the three dimensional unit sphere, which I'll call $S^{3}$. In Quantum Computing, $S^{3}$ is referred to as the Bloch Sphere. Now $S^{3}$ has nice algebraic structure; namely, the points on the unit sphere correspond precisely to the quaternions of norm $1$.
Recall, the Quaternions (or Hamiltonians) are the elements of: $$\mathbb{H} = \{ a + b\textbf{i} + c \textbf{j} + d\textbf{k} : a, b, c, d \in \mathbb{R}, \textbf{i}^{2} = \textbf{j}^{2} = \textbf{k}^{2} = -1, \textbf{ij} = -\textbf{ji}, \textbf{ik} = -\textbf{ki}, \textbf{jk} = -\textbf{kj} \}$$
That is, $\textbf{i}, \textbf{j}, \textbf{k}$ are square roots of $-1$ and anti-commute.
We can get our hands around the Hamiltonians by representing them as $2 \times 2$ unitary matrices, where the norm of a Hamiltonian element corresponds to the determinant of the corresponding matrix. So the Hamiltonians of norm $1$ are represented as special unitary matrices. Note that $U(2)$ and $SU(2)$ (the $2 \times 2$ unitary and special unitary matrices) form groups under matrix multiplication. Precisely, we are looking at the representation theory of a Lie group. Pollatsek's Lie Groups text is an accessible introduction to these ideas for undergrads, which only assumes Multivariable Calculus and Linear Algebra (https://www.amazon.com/Lie-Groups-Introduction-Mathematical-Association/dp/0883857596).
Quantum Computers are also very good at solving number theoretic and algebraic problems (e.g., factoring integers, Hidden Subgroup for Abelian groups, etc.). So having some number theory and group theory will be useful.
The key (and perhaps, only) algorithmic technique in Quantum Computing is the Fourier transform. In particular, it is nice to think of the Fourier transform over finite Abelian groups as a change of basis into the character basis. For an Abelian group $G$, the characters form an orthonormal basis of the group algebra $\mathbb{C}[G]$ (which is isomorphic to the vector space of functions from $G \to \mathbb{C}$). Having some Fourier Analysis and (again) Group Theory will be particularly helpful. Even if you don't have Group Theory, just having some Fourier Analysis will be very useful for picking up on the ideas.
From a Complexity standpoint, it would be useful to look over some randomized complexity classes like $\textsf{BPP}$. Note that $\textsf{BQP}$ generalizes $\textsf{BPP}$, rather than $\textsf{NP}$. Quantum Computing is inherently random, so having some perspective on error and randomness in classical computing will be useful.