Suppose the adversary has a quantum computer. If the adversary has time to run it on the public key before it becomes irrelevant, then every pre-quantum public-key signature scheme is broken. What if the adversary doesn't have time to run it on the public key before it becomes irrelevant? For example, in Bitcoin, a transaction is (very approximately) a signed statement saying
Please send 0.042 BTC to pubkey whose SHA-256 hash is 0x2ef20003e34f7113dfbb26b37e7544a657208aa4f11ffda8781d75e1bda23a09. Sincerely, pubkey 0x40e0cb242a51f749b028a4a3c0895000dc5c3bea58ab7d344e5d0a611529ef04.
As long as you use each public key only once, the adversary has only the time before the network has accepted the transaction to attempt to forge an alternative transaction before any future forgery of signatures by the sender of the transaction is inconsequential. If the adversary wants to forge signatures by the recipient of the transaction, they must also reverse SHA-256—a considerably harder problem. The adversary can try to parallelize the computation, but if theft is all that is at issue (which it may not be; false attribution or all manner of other things might be valuable to the adversary), then the parallelized computation can't cost more than 0.042 BTC before it's a waste of money.
However, this is not a proof of security against quantum computers, of course—it is at best an amusing thought in the attacker economist philosophy. It is also only the story for a single key. What happens if the adversary can break many keys simultaneously? As it happens, Pollard's $\rho$ algorithm breaks many keys simultaneously faster than many keys independently. (I'm not sure what the multi-target Shor story is.)
Now consider a hypothetical application beyond Bitcoin, where only select verifiers learn the public key at all, the verifiers whom the legitimate parties want to enable to verify signatures. What if the adversary doesn't even see the public key? Can the adversary recover the public key—and thereby break the cryptosystem with a quantum computer—from a signature, or a collection of signatures? (Even if the answer is no, of course, this doesn't rule out a quantum adversary's ability to forge signatures without recovering the public key, but while intuitively it seems unlikely, I won't address that extended question for now.)
In ECDSA over a curve $E/\mathbb F_p$, a signature under a public key $A \in E(\mathbb F_p)$ on a message $m \in \{0,1\}^*$ is a pair of $r \in \mathbb F_p$ and $s \in \mathbb Z/\ell\mathbb Z$, where $\ell = \#E(\mathbb F_p)$, satisfying the equation $$r = x([H(m)\,s^{-1}] B + [r s^{-1}] A),$$ where $B \in E(\mathbb F_p)$ is the standard base point. Knowledge of $a \in \mathbb Z/\ell\mathbb Z$ such that $A = [a]B$ makes it easy to solve for $s$ given uniform random $r$. However, we can also solve for public keys—not uniquely, but close enough to forge signatures with nonnegligible probability: by finding the points $R \in x^{-1}(r)$ with $x(R) = r$, so that $R \in \pm [H(m)\,s^{-1}] B + [r s^{-1}] A$, we can compute $$A \in [r^{-1} s] (R \pm [H(m)\,s^{-1}] B),$$ and so from a single signature it is easy to recover one of two public keys verifying the signature. Then an adversary with a quantum computer can solve the elliptic-curve discrete log problem with Shor's algorithm. Thus ECDSA does not provide security against this threat model.
What about Ed25519? An Ed25519 signature under a public key $A \in E(\mathbb F_p)$ on a message $m \in \{0,1\}^*$ is a pair $R \in E(\mathbb F_p)$ and $s \in \mathbb Z/\ell\mathbb Z$ such that $$[s] B = R + [H(\underline R \mathbin\Vert \underline A \mathbin\Vert m)] A.$$ If we had $\underline A$ (the encoding of the point $A$), then we could recover $$A = [H(\underline R \mathbin\Vert \underline A \mathbin\Vert m)^{-1}] ([s] B - R),$$ but this is begging the question. Does this mean Ed25519 provides security against this threat model? I don't know! This requires further analysis.
What about RSA signatures, say RSA-FDH? An RSA-FDH signature under a public key $n$ on a message $m$ is an element $s \in \mathbb Z/n\mathbb Z$ such that $s^3 \equiv H(m) \pmod n$, where $H\colon \{0,1\}^* \to \mathbb Z/n\mathbb Z$ is a uniform random function. If an adversary with a quantum computer learned $n$ they could use Shor's algorithm to factor it.
Now, a single signature doesn't reveal $n$. With a corpus of signatures, the adversary can solve the German tank problem to distinguish signatures under $n_0$ from signatures under $n_1$ and deanonymize signers—which doesn't guarantee the adversary can learn $n$ with enough precision to apply Shor's algorithm or hire Don Coppersmith to figure out a brilliant variant of it, but doesn't rule it out either.
What if we chose the first $s_i = H(m, i)^d \bmod n$ for $i = 0, 1, 2, \dots$ such that $s_i \bmod n < 2^{\lfloor\lg n\rfloor}$ by rejection sampling? This shouldn't reduce the security of the underlying signature scheme much: if an adversary could compute cube roots with nonnegligible probability given a signature scheme covering all elements of $\mathbb Z/n\mathbb Z$, then they could probably compute cube roots with at worst about half the probability given a signature scheme covering only elements below $2^{\lfloor\lg n\rfloor}$. (Caveat developer: I am just a pseudonymous bone-eating vulture on the internet, and I'm definitely not your cryptographer…and the first draft of this was completely wrong.)
