# Why are zk-STARK quantum secure?

I have a rough idea of how STARK work, but I want to know which part makes them quantum secure. Is it because when the prover generates the proof they use the random number from the Merkle root, which cannot be guessed by a quantum algorithm?

The only cryptographic primitive required for a zk-STARK is a cryptographically secure hash function, which we will denote $$H$$. Known quantum vulnerable forms of cryptography all depend on some other cryptographic primitive.
To prevent the generation of invalid proofs, the hash function $$H$$ needs to be pre-image resistant i.e. for a target output $$y$$ it should be hard to find an input $$x$$ such that $$H(x)=y$$. Now, if we know nothing about the function $$H$$ beyond the outputs that it produces, this is an example of an unstructured search problem that can be solved by Grover's algorithm on a sufficiently large and stable quantum computer in time roughly proportional to the square root of the image space. Indeed we know that Grover's algorithm is essentially the best possible approach to such problems. However, Grover's algorithm is highly non-parallelisable (to perform the search in 1/10 of the time we have to use 100x quantum computers) and it is argued that searching for solutions to 256-bit image spaces is not going to be possible for any reasonable projection of quantum computing capability.