Post-Quantum-Cryptography
IBM 的 Condor 量子處理器會執行 Shor 算法來破解 256 位橢圓曲線密鑰嗎？
昨天， IBM 宣布他們擁有一台名為 Osprey 的 433 位量子電腦。我能找到的新聞稿中沒有任何內容說明它是否可以執行 Shor 算法。
他們還表示，他們有望在明年發布 1121 位處理器“Condor”。
據我所知，Shor 的算法需要兩倍的密鑰位數，因此 256 位密鑰需要 512 個量子位才能破解。因此 Osprey 無法做到這一點，但 Condor 顯然可以做到。
256 位密鑰被廣泛使用——例如比特幣使用的 Ed25519，它是一種有效的 TLS 算法。
預計 Osprey 將能夠執行 Shor 的算法嗎？
如果可以，如何最好地減輕安全性損失？
不，這裡的問題是物理量子位和邏輯量子位之間的區別。Shor 算法對 256 位橢圓曲線的包絡估計的背面是 512 個邏輯量子位，但Roeteller 等人更準確的計算是 2330 個邏輯量子位。
邏輯量子位是理想化的計算資源，需要完美設計的物理量子位才能實現。Osprey 晶片及其同類產品的物理量子位會隨著時間的推移而退化，並以一定的錯誤率執行操作。相反，需要幾個 Osprey 類型的物理量子位來模擬使用量子糾錯的邏輯量子位的行為。估計在一小時內打破 256 位 ECC 所需的物理量子位的數量（這些物理量子位仍將符合高工程規範，可能超出 Condor 的規範）是 $ 317\times 10^6 $ 韋伯等人的每項工作。同樣，他們引用 $ 13\times 10^6 $ 這種高質量的物理量子比特可以在一天內解決這個問題。