据此，我知道我们需要 4^n 位来模拟 n 量子位量子计算机。我想知道是否可以在经典计算机上将 shor 的算法模拟到 15 倍？使用 shor 算法分解 15 需要多少个量子比特？
问问题
4602 次
2 回答
0
与经典计算机非常相似的量子计算机可以用 n 位呈现 2^n 不同的值。“周期查找子程序”中的 Shor 算法使用两个寄存器，可能和 n 一样大，2n + 1其中 n 是表示要分解的数字所需的位数。总的来说，您需要4n + 2量子位来运行 Shor 算法。
在降低量子比特要求方面做了一些工作。该实现仅2n + 3适用于一般数字的量子比特。
为了回答您的问题，您需要 4 个经典（或量子）位来表示 15，因此需要 62 个具有基本算法的量子位（您可能不会使用一些）。当然有一些解决方法，并且由于事先已知 15 的特殊属性，有一些成功的实验实现使用少至 7 个量子比特，但这不能用于 Shor 算法的一般数字因子。
当您在经典计算机上模拟量子计算机时，您通常希望用状态空间来表示它，其中每个基态对应一个可能的输出。这需要2^n虚数的维向量，实际位数取决于您对向量和虚数的实现。
于 2017-11-28T23:08:42.720 回答
0
您的问题的答案是 - 将 15（5 位数）分解为两倍，即 10 个量子位。
请参阅此视频以了解有关 shors 算法如何工作的详细信息。如果您亲自看到它，那应该可以澄清您的疑虑。
截至 2018 年 12 月 13 日，使用 Shor 算法的纯/未稀释/参考实现破解的最大任意 RSA 模数为 2048 位。RSA-2048 被破解。请参阅用于破解 RSA - 2048 的实现演示https://vimeo.com/306770425
于 2018-12-17T10:28:55.940 回答