Self Encrypting Drives (SED)
Many SSDs offer a "Self Encrypting Drive" feature where the encryption is completely transparent to the operating system. These require that you enter your drive password via a UEFI module and it will unlock the drive. These drives are always encrypting your data, even when SED is not enabled. Enabling SED causes the drive to encrypt the Data Encryption Key (DEK) with your password, thus requiring your password to access the data on the drives. In such a case, you need not worry about the prospects of data recovery.
OS-Based FDE
In the case of operating-system based FDE (Bitlocker, LUKS, FileVault, Veracrypt, etc.) things are a little different. There, encrypting the drive does require making a copy of all of the data from the plaintext to the ciphertext. (Notably, only Bitlocker and FileVault offer in-place encryption.)
From the paper you linked:
Second, overwriting the entire visible address space of an SSD twice is usually, but not always, sufficient to sanitize the drive.
So not all overwritten data is recoverable. After encrypting the drive, you can overwrite the slack space a few times to have a high likelihood of overwriting all of the underlying erase blocks.
That being said, encrypting the drive when new is still a best practice -- it avoids all these concerns, and ensures there's no time window where an attacker can get access to unencrypted data.
Side note on quantum computing: There is no evidence that quantum computing would allow breaking encrypted hard drives when used with a key length of 256 bits or longer. Grover's algorithm is the best known speedup for symmetric encryption, and it has the effect of halving the key length. (So a 256 bit key offers 128 bits of effectiveness against a quantum computer.) Additionally, cryptographers do not believe even well-funded adversaries currently have large scale quantum computers, but that is likely to change in the next 10-15 years.