COMS 4281 Problem Set 4
COMS 4281 – Intro to Quantum Computing
Problem Set 4: Hamiltonians, Algorithms, and Complexity
Due: November 20, 11�59pm.
Collaboration is allowed and encouraged (teams of at most 3). Please read the syllabus
carefully for the guidlines regarding collaboration. In particular, everyone must write their
own solutions in their own words.
Write your collaborators here:
Problem 1: Hamiltonian Math
Problem 1.1
Let be a Hamiltonian and let be a ground state, i.e., it minimizes over all
states. Show that is an eigenvector.
Problem 1.2
Let be a Hamiltonian and let denote some initial state with average energy
Let denote the time evolution of with respect to the Hamiltonian . In other
Show that the energy of the state with respect to is still . In other words, show
that time evolution of a state with respect to a Hamiltonian conserves energy.
In [ ]: %run utils.py
H |ψ⟩ ⟨ψ| H |ψ⟩
E = ⟨ψ(0)| H |ψ(0)⟩
|ψ(t)⟩ |ψ(0)⟩ H
|ψ(t)⟩ = e−iHt |ψ(0)⟩ .
|ψ(t)⟩ H E
11/6/22, 9:15 PM pset4
localhost:8888/nbconvert/html/pset4.ipynb?download=false 2/4
Problem 2: The 1D Ising model
Problem 2.1
Recall the 1-dimensional Ising model, which is a Hamiltonian describing a bunch of magnets
on a line:
where is a real parameter that represents the strength of the global magnetic field
relative to the interactions between neighboring magnets.
Fix a string and consider the corresponding -qubit basis state
Give a formula for the quantity in terms of the strings and the parameter .
Use this to deduce the spectral decomposition (i.e. find its eigenvectors and eigenvalues) of
, as a function of .
Problem 2.2
Suppose . What is the minimum energy of and what are the ground states of ?
What is the maximum energy of and what states achieve the maximum energy?
Problem 2.3
Suppose . What is the ground energy and ground states of ? What about when
Problem 2.4
Zj ⊗ Zj+1 + μ
x ∈ {0, 1}n n
|x⟩ = |x1, … , xn⟩
⟨x| H |x⟩ x μ
11/6/22, 9:15 PM pset4
localhost:8888/nbconvert/html/pset4.ipynb?download=false 3/4
Give a qualitative description of what the ground states of are, depending on . What
happens as or ? Are there “critical points” of where the behavior of the
ground states seem to change?
Problem 3: Quantum Graph Algorithms
Problem 3.1
In this problem you will design a quantum query algorithm to determine whether a graph is
connected (i.e. there is a path between every pair of vertices). Let be an -vertex
undirected graph and let denote the adjacency matrix for (i.e., if and
only if there is an edge between vertices and in the graph). Suppose you are given
access to an oracle that, on a basis state for some and ,
maps it to the state . In other words, if is an edge in the graph, then
, and otherwise .
Design and analyze a quantum algorithm that makes at most calls to the
oracle and determines if the graph is connected with probability at least . To
design your algorithm, you may use any classical graph algorithm (depth-first search,
breadth-first search, etc.), combined with any of the quantum algorithms we have learned in
class as a subroutine.
This constitutes a quantum speedup, because any classical algorithm must make
queries to the adjacency matrix to determine whether a graph is connected (even if the
algorithm is randomized).
Hint: if you use Grover’s algorithm that makes queries as we’ve learned about it in
class, be mindful that it has some probability of error. In general, if the number of solutions
are not known ahead of time, then there is some constant probability of error (say at least
Problem 3.2
Show that any quantum algorithm must make at least queries to the oracle in
order to determine whether the graph is connected.
Hint: You can assume the optimality of Grover’s algorithm for unstructured search.
μ → ∞ μ → −∞ μ
A n × n G Aij = 1
V |i, j, a⟩ i, j ∈ [n] a ∈ {0, 1}
∣∣i, j, a ⊕ Aij⟩ (i, j)
V |i, j, a⟩ = |i, j, a ⊕ 1⟩ V |i, j, a⟩ = |i, j, a⟩
O(n3/2 log n)
11/6/22, 9:15 PM pset4
localhost:8888/nbconvert/html/pset4.ipynb?download=false 4/4
Bonus: Prove that queries to the oracle are needed.
Problem 4: NP-hardness of estimating output
probabilities
Suppose that there existed a classical algorithm that does the following amazing thing:
when given input where describes a quantum circuit acting on qubits with
gates, and is an -bit string, it outputs a number such that
is the probability that, when measuring the final state of on all the all zeroes input, yields
measurement outcome . In other words, the output of the algorithm on is a
number that equal to up to digits of precision. Furthermore, the algorithm
runs in time polynomial in and .
Show that this would imply by showing that, if such an amazing algorithm
existed, then one could use to solve 3SAT (or your favorite -complete problem) in
polynomial time. Therefore, one shouldn’t expect it to be possible to efficiently calculate
output probabilities of general quantum circuits. Recall that in the 3SAT problem, you’re
given a boolean formula of the form , and the
goal is to determine whether there exists an assignment to the variables that satisfies the
Hint: you’ll want show that for an instance of a -complete problem (such as 3SAT),
you can transform that problem into a polynomial-sized quantum circuit such that the
answer to the problem (whether it’s satisfiable, graph colorable, etc.) can be encoded
into the probability of some outcome of measuring the circuit on the all zeroes input.
(C, x) C n m
|α − p(C, x)| ≤ 2−10n
p(C, x) = |⟨x| C |0n⟩|
x A (C, x)
p(C, x) 10n A
(x1 ∨ x2 ∨ ¬x5) ∧ (¬x7 ∨ x1 ∨ ¬x11) ∧ ⋯