양자 컴퓨터

위키백과 ― 우리 모두의 백과사전.

The Bloch sphere is a representation of a qubit, the fundamental building block of quantum computers.
The Bloch sphere is a representation of a qubit, the fundamental building block of quantum computers.

양자 컴퓨터(quantum computer)는 얽힘(entanglement)이나 중첩(superposition) 같은 양자역학적인 현상을 이용하여 자료를 처리하는 계산 기계이다. 고전적인(전통적인) 컴퓨터에서 자료의 양은 비트로 측정된다. 양자 컴퓨터에서 자료는 큐비트으로 측정된다. 양자 계산의 기본적인 원칙은 입자의 양자적 특성이 자료를 나타내고 구조화 할 수 있다는 것과 양자적 메카니즘이 고안되어 이러한 자료들에 대한 연산을 수행할 수 있도록 만들어 질 수 있다는 것에 기한다.

양자 컴퓨팅이 여전히 유아기에 있지만, 매우 작은 수의 큐비트을 가지고 양자 수치 계산이 수행되는지에 관한 실험들이 행해져 왔다.

[편집] Quantum computing in computational complexity theory

The suspected relationship of BQP to other problem spaces
The suspected relationship of BQP to other problem spaces[1]

This section surveys what is currently known mathematically about the power of quantum computers. It describes the known results from computational complexity theory and the theory of computation dealing with quantum computers.

The class of problems that can be efficiently solved by quantum computers is called BQP, for "bounded error, quantum, polynomial time". Quantum computers only run randomized algorithms, so BQP on quantum computers is the counterpart of BPP on classical computers. It is defined as the set of problems solvable with a polynomial-time algorithm, whose probability of error is bounded away from one quarter (Nielsen & Chuang 2000). A quantum computer is said to "solve" a problem if, for every instance, its answer will be right with high probability. If that solution runs in polynomial time, then that problem is in BQP.

BQP is suspected to be disjoint from NP-complete and a strict superset of P, but that is not known. Both integer factorization and discrete log are in BQP. Both of these problems are NP problems suspected to be outside BPP, and hence outside P. Both are suspected to not be NP-complete. There is a common misconception that quantum computers can solve NP-complete problems in polynomial time. That is not known to be true, and is generally suspected to be false.

An operator for a quantum computer can be thought of as changing a vector by multiplying it with a particular matrix. Multiplication by a matrix is a linear operation. Daniel S. Abrams and Seth Lloyd have shown that if a quantum computer could be designed with nonlinear operators, then it could solve NP-complete problems in polynomial time. It could even do so for #P-complete problems. They do not believe that such a machine is possible.

Although quantum computers are sometimes faster than classical computers, ones of the types described above can't solve any problems that classical computers can't solve, given enough time and memory (albeit possibly an amount that could never practically be brought to bear). A Turing machine can simulate these quantum computers, so such a quantum computer could never solve an undecidable problem like the halting problem. The existence of "standard" quantum computers does not disprove the Church-Turing thesis (Nielsen and Chuang 2000).

Very recently, many researchers have begun to investigate the possibility of using quantum mechanics for hypercomputation - that is, solving undecidable problems. Such claims have been met with considerable skepticism as to whether it is even theoretically possible; see the hypercomputation article for more details.

[편집] 참고

이 문서는 컴퓨터에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.