量子计算和加密破解 [英] Quantum Computing and Encryption Breaking
问题描述
前言：量子电脑是奇怪的野兽，我们还没有驯服到这一点的有用性支持它们的理论是抽象的和数学的，所以关于它们如何能够比古典计算机更有效率的任何讨论将不可避免地需要很长的时间。您至少需要理解线性代数和量子力学的本科生了解细节，但我会尽力表达我的有限的理解。
量子计算的基本前提是量子叠加。这个想法是，如您所说，量子系统（例如量子位或者量子位，或正常位的量子模拟）可以不仅存在于 正因为如此， 由于量子计算机的这个属性，它似乎是一个银弹，可以解决任何问题比古典计算机指数快。但这不是那么简单：问题是，一旦你观察到你的计算结果，它会崩溃（如上所述），只是其中一个计算的结果，而你失去了所有其他的一些。 量子计算/算法的领域是关于通过操纵量子现象来解决这个问题的工作，以比在古典计算机上可能的操作更少的操作来提取信息。事实证明，比任何可能的经典对手都要快一些量子算法是非常困难的。 您所要求的例子是量子密码分析的例子。认为量子计算机可能能够打破某些加密算法：具体来说，RSA算法依赖于找到非常大的整数的主要因素的困难。允许这一点的算法称为 Shor's算法，它可以将整数乘以多项式时间复杂。相比之下，问题的最佳经典算法具有（几乎）指数时间的复杂性，而且问题因此被认为是难处理的。 如果你想更深入地了解这一点，就可以得到一些关于线性代数和量子力学的书，并得到舒适。如果你想要一些澄清，我会看看我能做什么！ Aside ：更好地了解量子叠加的想法，从概率上考虑。想象一下，你翻了一个硬币，抓住它在你的手上，盖住，所以你看不到它。 作为一个非常脆弱的类比，硬币可以被认为是头和尾状态的叠加：每个人的概率为0.5（并且自然地，因为有两个状态，这些概率加起来为1）。当你把手拿走并直接观察硬币时，它会折叠到头部状态或尾部状态，因此这个状态的概率变为1，而另一个变为0.有一种想法，我想，是一套平衡的尺度，直到观察，在这一点上它提示一边，因为我们的知识的系统增加，一个国家成为真正的状态。 当然，我们不认为硬币是一个量子系统：对于所有实际的目的，硬币有一个明确的状态，即使我们看不到它。然而，对于真正的量子系统（例如个人粒子被困在一个框），我们可以不用这样想。在量子力学的常规解释下，粒子从根本上没有确定的位置，但同时存在于所有可能的位置。只有观察到它的位置在空间上受到限制（尽管仅在一定程度上;参见不确定性原则），即使这是纯粹随机的，只有概率确定。 顺便说一句，量子系统不仅限于只有两个可观察状态（那些是称为两级系统）。有些具有大而有限的数字，有些数字有无数的数字（例如在一个框中的粒子 或谐波振荡器），有些甚至有无数的数字（如作为免费粒子的位置，不限于个别点在空间）。 I read a while back that Quantum Computers can break most types of hashing and encryption in use today in a very short amount of time(I believe it was mere minutes). How is it possible? I've tried reading articles about it but I get lost at the Preamble: Quantum computers are strange beasts that we really haven't yet tamed to the point of usefulness. The theory that underpins them is abstract and mathematical, so any discussion of how they can be more efficient than classical computers will inevitably be long and involved. You'll need at least an undergraduate understanding of linear algebra and quantum mechanics to understand the details, but I'll try to convey my limited understanding! The basic premise of quantum computation is quantum superposition. The idea is that a quantum system (such as a quantum bit, or qubit, the quantum analogue of a normal bit) can, as you say, exist not only in the Because of this, a register of Because of this property of quantum computers, it may seem like they're a silver bullet that can solve any problem exponentially faster than a classical computer. But it's not that simple: the problem is that once you observe the result of your computation, it collapses (as I mentioned above) into the result of just one of the computations – and you lose all of the others. The field of quantum computation/algorithms is all about trying work around this problem by manipulating quantum phenomena to extract information in fewer operations than would be possible on a classical computer. It turns out that it's very difficult to contrive a "quantum algorithm" that is faster than any possible classical counterpart. The example you ask about is that of quantum cryptanalysis. It's thought that quantum computers might be able to "break" certain encryption algorithms: specifically, the RSA algorithm, which relies on the difficulty of finding the prime factors of very large integers. The algorithm which allows for this is called Shor's algorithm, which can factor integers with polynomial time complexity. By contrast the best classical algorithm for the problem has (almost) exponential time complexity, and the problem is hence considered "intractable". If you want a deeper understanding of this, get a few books on linear algebra and quantum mechanics and get comfortable. If you want some clarification, I'll see what I can do! Aside: to better understand the idea of quantum superposition, think in terms of probabilities. Imagine you flip a coin and catch it on your hand, covered so that you can't see it. As a very tenuous analogy, the coin can be thought of as being in a superposition of the heads and tails "states": each one has a probability of 0.5 (and, naturally, since there are two states, these probabilities add up to 1). When you take your hand away and observe the coin directly, it collapses into either the heads state or the tails state, and so the probability of this state becomes 1, while the other becomes 0. One way to think about it, I suppose, is a set of scales that is balanced until observation, at which point it tips to one side as our knowledge of the system increases and one state becomes the "real" state. Of course, we don't think of the coin as a quantum system: for all practical purposes, the coin has a definite state, even if we can't see it. For genuine quantum systems, however (such as an individual particle trapped in a box), we can't think about it in this way. Under the conventional interpretation of quantum mechanics, the particle fundamentally has no definite position, but exists in all possible positions at once. Only upon observation is its position constrained in space (though only to a limited degree; cf. uncertainty principle), and even this is purely random and determined only by probability. By the way, quantum systems are not restricted to having just two observable states (those that do are called two-level systems). Some have a large but finite number, some have a countably infinite number (such as a "particle in a box" or a harmonic oscillator), and some even have an uncountably infinite number (such as a free particle's position, which isn't constrained to individual points in space). 这篇关于量子计算和加密破解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！ 0中和 1 状态（称为系统的计算基础状态），也可以是两者的任意组合使得每个具有与其相关联的幅度）。当系统被某人观察时，量子位的状态将其折叠成其基础之一（你可能已经听说过薛定er猫的想法实验，这与之相关）。 / p>
n qubits的注册具有 2 ^ n 它自己的基本状态（这些是您可以观察寄存器的状态;想象一个经典的n位整数）。由于寄存器可以同时存在于所有这些状态的叠加中，所以可以将计算应用于所有的 2 ^ n 寄存器状态，而不仅仅是其中之一。这被称为量子并行性。
a quantum bit can be 1, 0, or something else. Can someone explain how this relates to cracking such algorithms in plain English without all the fancy maths?
0 and 1 states (called the computational basis states of the system), but also in any combination of the two (so that each has an amplitude associated with it). When the system is observed by someone, the qubit's state collapses into one of its basis states (you may have heard of the Schrödinger's cat thought experiment, which is related to this).n qubits has 2^n basis states of its own (these are the states that you could observe the register being in; imagine a classical n-bit integer). Since the register can exist in a superposition of all these states at once, it is possible to apply a computation to all 2^n register states rather than just one of them. This is called quantum parallelism.
