user95422: In a hypothetical future where a quantum computer is able to break the cryptography protecting the bitcoin private key, one of the solution would be to move our coins to quantum safe resistant addresses before it happens.
How could this switch look like, does every UTXO have to be published on the blockchain on which new quantum resistant address it is moving to, and what would these addresses look like?

user137501: There has been some literature discussing this and a migration strategy:

Giechaskiel, I., Cremers, C., Rasmussen, K.B. (2016). On Bitcoin Security in the Presence of Broken Cryptographic Primitives
Stewart, I., Ilie, D., Zamyatin, A., Werner, S., Torshizi, M.F., Knottenbelt, W.J. (2018). Committing to Quantum Resistance: A Slow Defence for Bitcoin against a Fast Quantum Computing Attack
Ciulei, A.T., Crețu, M.C., Simion, E. (2022). Preparation for Post-Quantum era: a survey about blockchain schemes from a post-quantum perspective

The 2nd referenced paper describes a commit-reveal scheme that would avoid having your funds stolen when you want to migrate them to some new, quantum-resistant address.
The new addresses would pretty much look the same: a string of characters, with maybe few bits of difference in starting characters to encode the use of some new scheme. If collision resistance is required they'd also have to be a little longer (384 bits). Quantum preimage resistance is already achieved with SegWit 256-bit addresses (even though the underlying key is vulnerable).
In fact, assuming some upgrades to Bitcoin Script opcodes to have QC-resistant signature opcodes, then for many applications quantum-resistant addresses could look exactly the same as current P2WSH addresses.
So addresses wouldn't be affected much. However, transactions would get much bigger, since the input script would then have to include a bigger public key and signature. For example, SPHINICS uses 1KB keys and 41KB signatures so in that case the address would have to be about 7 times longer and signature about 645 times longer! Note that, with SegWit, the big signature data wouldn't count against the legacy 1MB blocksize limit but it would count against the 4MB SegWit block weight limit so we could fit much less transactions. To allow the same number of transactions, some protocol upgrade would have to be rolled out to make room for bigger signature data.

95422: <p>In a hypothetical future where a quantum computer is able to break the cryptography protecting the bitcoin private key, one of the solution would be to move our coins to quantum safe resistant addresses before it happens.</p>
<p>How could this switch look like, does every UTXO have to be published on the blockchain on which new quantum resistant address it is moving to, and what would these addresses look like?</p>
 137501: <p>There has been some literature discussing this and a migration strategy:</p>
<ul>
<li><a href="https://link.springer.com/chapter/10.1007/978-3-319-45741-3_11" rel="nofollow noreferrer">Giechaskiel, I., Cremers, C., Rasmussen, K.B. (2016). On Bitcoin Security in the Presence of Broken Cryptographic Primitives</a></li>
<li><a href="https://eprint.iacr.org/2018/213.pdf" rel="nofollow noreferrer">Stewart, I., Ilie, D., Zamyatin, A., Werner, S., Torshizi, M.F., Knottenbelt, W.J. (2018). Committing to Quantum Resistance: A Slow Defence for Bitcoin against a Fast Quantum Computing Attack</a></li>
<li><a href="https://eprint.iacr.org/2022/026.pdf" rel="nofollow noreferrer">Ciulei, A.T., Crețu, M.C., Simion, E. (2022). Preparation for Post-Quantum era: a survey about blockchain schemes from a post-quantum perspective</a></li>
</ul>
<p>The 2nd referenced paper describes a commit-reveal scheme that would avoid having your funds stolen when you want to migrate them to some new, quantum-resistant address.</p>
<p>The new addresses would pretty much look the same: a string of characters, with maybe few bits of difference in starting characters to encode the use of some new scheme. If collision resistance is required they'd also have to be a little longer (384 bits). Quantum preimage resistance is already achieved with SegWit 256-bit addresses (even though the underlying key is vulnerable).</p>
<p>In fact, assuming some upgrades to Bitcoin Script opcodes to have QC-resistant signature opcodes, then for many applications quantum-resistant addresses could look exactly the same as current <a href="https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki#P2WSH" rel="nofollow noreferrer">P2WSH</a> addresses.</p>
<p>So addresses wouldn't be affected much. However, transactions would get much bigger, since the input script would then have to include a bigger public key and signature. For example, <a href="https://sphincs.cr.yp.to/" rel="nofollow noreferrer">SPHINICS</a> uses 1KB keys and 41KB signatures so in that case the address would have to be about 7 times longer and signature about 645 times longer! Note that, with SegWit, the big signature data wouldn't count against the legacy 1MB blocksize limit but it would count against the 4MB SegWit block weight limit so we could fit much less transactions. To allow the same number of transactions, some protocol upgrade would have to be rolled out to make room for bigger signature data.</p>
