...
The UXTO constraint may never be solved in an acceptable (sub)linear way, or the solution(s) could for political reasons never be implemented in BTC.
...
Almost certainly 'never' by any realistic definition of various things.
...
Solving 'the UTXO problem' would require what is by most definitions 'magic'. Perhaps some future quantum-effect storage, communications, and processing schemes could 'solve' the problem but I'm not expecting to pick up such technology at Fry's by the next holiday season (Moore's law notwithstanding.)
A comment from chriswilmer got me thinking…
The UTXO set is actually bounded. The total amount of satoshis that will ever exists is
(21x10^6) x (10^8) = 2.1 x 10^15 = 2.1 "peta-sats"
The UTXO set is maximized if every output is exactly 1 satoshi; in this case, the UTXO set consists of 2.1x10^15 outputs.
For each output, let's assume we store the transaction hash (32 bytes), the value (8 bytes max), and the scriptpubkey (25 bytes for P2PkH), which is a total of 65 bytes. So, a reasonable "worst case" upper bound on the size of the UTXO set is:
(2.1x10^15) x (65 bytes) = 137 petabytes.
How much memory is this? A quick google search turned up 128 gigabyte microSD cards:
To store the worst-case UTXO set on an array of these cards would require about one million of them:
(137 x 10^15) / (128 x 10^9) = 1.07 x 10^6.
This calculation shows that storing the
worst case UTXO set is currently beyond the limits of a home user, but it's actually within the limits of large data centers such as the
Prineville campus for Facebook that stores 1,000 petabytes of data...
...OK, now let's be reasonable! Let's assume that 10 billion people on earth each control about 4 unspent outputs on average. That's a total of 40 billion outputs, or
(40 x 10^9) x (65 bytes) = 2.6 terabytes
With these assumptions, it now only takes about 20 of those SD cards to store the UTXO set:
(2.6 x 10^12) / (128 x 10^9) = 20.3,
or, three 1-terrabyte SSDs, for a total cost of about $1,500.
Of course, by the time there's a need to store this much data, we will likely have special-purpose hardware to do so quite efficiently.
TLDR:
1. Large data centers could already store the UTXO set even if every satoshi was a unique unspent output.
2. Under more reasonable assumptions, power users and small businesses should be able to store the UTXO set even if 10 billion people each had 4 unspent outputs.