CS260 Study Guide

10a. Explain quantum operators

• What is superposition?
• What is entanglement?
• What are some properties of quantum operators?

A state vector for a quantum computational system is defined as a vector that contains all the information necessary for performing quantum computations. For example, a single qubit state vector is of the form

|𝜓> = a|0> + b|1>

where $Ia|^2+|b|^2 = 1$. A linear superposition is a linear combination of a set of basis states. In the above single qubit example, the state vector |𝜓> is said to be in a linear superposition of the computational basis kets $|0>$ and $|1>$. The probability of measuring a system in state $|0>$ is $Ia|^2$, and the probability of measuring a system in state $|1> is Ib|^2$. The state vector for a two-qubit system, in general, has the form

|𝜓> = a₀₀|00> + a₀₁|01>+ a₁₀|10>+ a₁₁|11>

where the sum of the amplitude magnitudes squared is now normalized to a value of 1. Higher qubit systems can be built up from tensor products of lower qubit systems; however, it is not always the case that a higher qubit system can be expressed in terms of lower qubit systems. Consider a two-qubit system that looks like

|𝜓> = a₀₀|00> + a₁₁|11>

This system is known as an entangled system and cannot be built up from a tensor product of single qubit states. You should understand the concepts of superposition and entanglement in quantum systems.

Quantum operators are those that operate on state vectors that define a quantum state. Quantum computation applies a set of quantum operators to a state vector to achieve a specific computation. In quantum computation, operators are usually expressed as a matrix that operates on state vectors. Typical operators applied in quantum computation are the Hadamard matrix, Pauli spin matrices, rotation gates, Fourier operators, permutation matrices, Toffoli gates, and CNOT gates. Quantum computation must be reversible, and this constraint implies that all quantum operators must be unitary (that is, the Hermitian adjoint must be equal to the matrix inverse). While this is not a course in quantum computation, you should be familiar with basic concepts involving reversible computation, unitary matrices, and quantum operators.

To review, see:

• Introduction to Quantum Computation
• Cryptographic Implications
• The Deutsch-Jozsa Algorithm and QKD

10b. Apply the order-finding problem to factoring

• What is the order-finding problem?
• How is factoring related to order finding?
• Why is order finding important to cryptography?

Nontrivial roots of unity are defined as nontrivial solutions to the equation

s²=1 mod N

The rearrangement of this equation as

(s+1)(s-1)=s²-1 = 0 mod N

is a path to factoring the composite number N. If the gcd(q,N)=1 for some q in the congruence modulo N, then some m is guaranteed to satisfy

q^m = 1 mod N

where m is the order of q. The order-finding problem is defined as the process of finding m such that

q^m = 1 mod N.

Therefore, finding nontrivial roots of unity to factor N can be translated into the order-finding problem. Since there is currently no known method to predict the successive powers of q, determining the value of m is considered computationally difficult as N becomes large. Since RSA depends upon factoring a composite number N, solving the order-finding problem is directly relevant to cryptography. At this point in the course, you should have code available to compute the order of an element q by computing successive powers (which may involve either successively computing q**m or using your repeated squaring algorithm).

To review, see:

• Cryptographic Implications
• Factoring by Perfect Squares
• Overview of Shor's Algorithm

10c. Explain Shor's algorithm

• What is Shor's algorithm?
• How is order finding related to Shor's algorithm?
• What are some quantum operators used in Shor's algorithm?

There is no known classical factoring algorithm that is computationally efficient. This is why systems such as RSA have been considered to be computationally secure. Shor's algorithm is a quantum-based scheme that is efficient for factoring numbers and solving the discrete logarithm problem. Understanding that some parts of Shor's algorithm can be solved efficiently via classical means is important. For example, verifying that the gcd(q,N)=1 for some value q in the congruence modulo N can readily be performed using the Euclidean algorithm. Shor's algorithm turns the order-finding problem into a period-finding problem and creates quantum operators that can successively exponentiate. The architecture for Shor's approach to solving the order-finding problem involves Hadamard operators, exponentiation operators, and an inverse Fourier operator. The inverse Fourier operator is applied to perform what is known as phase estimation. While this is not a course in quantum computation, you should be familiar with the concepts necessary for understanding how Shor's algorithm works and why it can be used to solve the factoring problem.

To review, see:

• Breaking RSA
• Shor's Quantum Architecture
• Breaking RSA Using Shor's Algorithm

Unit 10 Vocabulary

This vocabulary list includes terms you will need to know to successfully complete the final exam.

• linear superposition
• nontrivial roots of unity
• order-finding problem
• quantum computation
• quantum operator
• Shor's algorithm
• state vector