next up previous
Next: 4.5.1 Forming the Initial Up: 4 Solving 1-SAT Previous: 4.4 Performance of the

4.5 Implementation 

Conceptually, the operation of Eq. (12) can be performed classically by matrix multiplication. However, since the matrices have tex2html_wrap_inline1628 rows and columns, this is not be a practical algorithm. As described in §2, quantum computers can rapidly perform many matrix operations of this size. Here we show how this is possible for the operations used by this algorithm.

For describing the implementation, it is useful to denote the individual components in a superposition explicitly. Traditionally, this is done using the ket notation introduced by Dirac [18]. For instance, the superposition described by the state vector of Eq. (1) is equivalently written as tex2html_wrap_inline2276 where tex2html_wrap_inline2278 just represents a unit basis vector corresponding to the assignment s. An example of these alternate, and equivalent, notations is:


Tad Hogg
Feb. 1999