1.Rank the algorithms for matrix multiplication by time complexity from best to worst. Algorithms: Strassen, Nave approach, and Coppersmith-Winograd.

1 (Best)

2

3 (Worst)

question 2.State the Big O time complexity for each algorithm that performs matrix multiplication. Example: (()) for some function of .

Nave approach

Strassen (Divide & Conquer)

Coppersmith-Winograd

question 3. Quantum gates perform a transformation on 1 or more qubits. These transforms have a corresponding matrix.

What is the size of the matrix for a single-qubit gate?

What is the size of the matrix for a 3-qubit gate?

question 4. What does ground state mean in the context of quantum computing?

question 5. Given the quantum superposition state | = |0 + |1, answer the following.

What is the amplitude of the vector in the |0 direction?

What is the amplitude of the vector in the |1 direction?

What is the probability of the vector in the |0 direction?

What is the probability of the vector in the |1 direction?

question 6. If a Hadamard gate followed by measurement is applied to each qubit in a 3-qubit quantum circuit, what is the expected result of running the circuit for 8192 shots on a simulator? Write your answer in terms of number of shots per state.