Quantum computing: a brief introduction andsome research topics
Frank (Peng) Fu
Computer Science and Engineering Department, UofSC

1

Basics of quantum computing: qubits▶ Bit. |0⟩ =  
10, |1⟩ =.
01 α▶ Qubit. |ϕ⟩ = α|0⟩ + β|1⟩ =, whereβ
α, β ∈ C, |α|2 + |β|2 = 1.
▶ Multi-qubits are represented by a tensor product.
|ϕ1 ⟩ ⊗ |ϕ2 ⟩ = (α1 |0⟩ + β1 |1⟩) ⊗ (α2 |0⟩ + β2 |1⟩)
= α1 α2 |00⟩ + α1 β2 |01⟩ + β1 α2 |10⟩ + β1 β2 |11⟩Or,

α1β1

α1 α2  α1 β2 α⊗ 2 =
 β1 α2  .
β2β1 β22

Basics of quantum computing: quantum gates

One way to update qubits is via unitary operations.
▶ A complex matrix is unitary if UU † = U † U = I .
▶ Linearity: U(α|0⟩ + β|1⟩) = αU|0⟩ + βU|1⟩.

3

Quantum gates▶ Hadamard gate.
√H|0⟩ = |+⟩ = 1/√2(|0⟩ + |1⟩)
H|1⟩ = |−⟩ = 1/ 2(|0⟩ − |1⟩)
▶ Phase gate.

HS|0⟩ = |0⟩
S|1⟩ = i|1⟩
▶ T gate.

ST |0⟩ = |0⟩
T |1⟩ = ω|1⟩, where ω 2 = i▶ CNOT gate.

TCNOT|00⟩ = |00⟩, CNOT|01⟩ = |01⟩
CNOT|10⟩ = |11⟩, CNOT|11⟩ = |10⟩•

4

Measurement

Measurement is used to obtain the result of a computation.
M▶ M(α|0⟩ + β|1⟩) = |0⟩ with probability |α|2 .
▶ M(α|0⟩ + β|1⟩) = |1⟩ with probability |β|2 .

5Quantum circuit diagram

•|ϕ⟩
|0⟩
|0⟩H

•

H

•

MM

•
X

Z|ϕ⟩Note that Z = S 2 and X = HZH is the not-gate.

6

Fun facts▶ The gate set {H, S, CNOT } is called Clifford gate set.
Quantum circuits consists of only Clifford gates can beefficiently simulated using classical computer.
▶ Clifford gates + T gate is universal, i.e., any unitary operations
can be approximated by Clifford + T up to epsilon.
▶ T gates are known to be hard to implement, they dominate
the cost of running a quantum circuit.
▶ Programming with only Clifford gates + T is an art, inpractice people also work with a few extra gates, e.g., rotation
gates, Toffoli gate.

7

Research topic 1: T-count optimization

How to reduce the number of T gates or other resource intensivegates (e.g. rotation, toffoli) in a given circuit?
▶ Existing methods: gate cancellation (e.g., T 2 = S), path
polynomials (for rotations and CNOT circuits).
▶ Recent work: Automated optimization of large quantum
circuits with continuous parameters, Nam et al. 2018.

8

Research topic 2: Circuit identity verification

Given two circuits, how do we know they are equal?
▶ Related to Topic 1, how do we know the optimized circuit iscorrect?
▶ Existing methods: matrix/algebraic formulation, path-sum
formalism (Amy 2018), circuit equational theory (Clément etal. 2023).

9

Research topic 3: Hamiltonian simulation▶ Physicist says: natural evolves according to Schrodinger’sequation.
v ′ = −iHv
▶ The solution to the above differential equation is the following.
v = e −iH v0 ,where H is called Hamiltonian, it is a hermitian matrix, i.e.,
H = H †.
▶ Hamiltonian simulation problem: Given a Hamiltonian H, finda quantum circuit that implements e −iH .
▶ In practice H may be sparse but can be exponentially large, it
is hard to implement e −iH classically.
▶ Existing methods: Product formulas (Suzuki 1991), Quantum
Signal Processing (Low and Chuang 2017).
10

Research topic 4: Quantum resource analysis

How much resource does it take to run a useful quantum algorithm?
▶ Resource: number of qubits, number of T-gates, total running
time (circuit depth), hardware resources etc.
▶ Existing tools: BenchQ (Zapata AI), QUALTRAN (GoogleQuantum AI), Azure Quantum Resource Estimator (MicrosoftQuantum), pyLIQTR (MIT Lincoln Lab), Symbolic QRE
Engine (PsiQuantum).

11Research topic 5: Quantum programming languages

How do we design and build infrastructure to provide someguarantees about our programs before sending it to quantumcomputer?
▶ Qiskit (IBM).
▶ Cirq (Google).
▶ Quipper.
▶ Proto-Quipper.

12

Research topic 6: Programming quantum computer

Our department has access to IBM’s 127 qubits quantum
computers. What kind of programs can we run on them toillustrate the usefulness of quantum computer?
Some potential candidates:▶ Quantum Arithmetics.
▶ Quantum Fourier Transform.
▶ Other possibilities?

13Research topic 7: Quantum Computing and AI?

Quantum machine learning?

14