Rapid advance of quantum technologies demands novel mathematical tools for engineering complex quantum systems. Characterization of the structural and dynamical properties of large-scale quantum devices, e.g., a quantum computer with 100 qubits, is among the current challenges. The major obstacle is the size of the Hilbert space and therefore the required experimental and computational resources that grow exponentially with the number of the system components. Recently, compressed sensing method has been applied for efficient characterization of quantum systems. Originally developed in classical signal processing, compressed sensing is a method to compress high-dimensional signals with a small number of measurements assuming that the signals live on a low-dimensional manifold, and then to
reliably reconstruct them. In this presentation, I talk about the compressed sensing theory for quantum inversion problems, its first experimental realization, and the new problems motivated by quantum applications.

[1] A. Shabani, R. L. Kosut, M. Mohseni, H. Rabitz, M. A. Broome,
M.P. Almeida, A. Fedrizzi and A. G. White,
”Efficient measurement of quantum dynamics via compressive sensing”,
Phys. Rev. Lett 106, 100401 (2011).

[2] A. Shabani, M.Mohseni, S. Lloyd, R. L. Kosut and H. Rabitz,
”Estimation of many-body quantum Hamiltonians via compressive sensing”,
Phys. Rev. A 84, 012107 (2011).

Practically every result that is presented in an elementary course
in number theory (i.e. Math 104 at UCSD) is used in the proof that this
joint work with D. Meyer works and gives an algorithm in the quantum
computing class analogous to P (polynomial).

Kirchhoff's Matrix Tree Theorem is one of the classical results in
spectral graph theory and it gives a formula for the number of
spanning trees of a graph in terms of the eigenvalues of its
Laplacian.
In 1973, Chvatal introduced the notion of graph toughness and made two
important conjectures: 1. Any graph with sufficiently large toughness
is Hamiltonian. 2. Any graph with sufficiently large toughness is
pancyclic.
The first conjecture is still open, but the second conjecture was
disproved by Alon who showed that there exist graphs with arbitrarily
large toughness and girth. The key to Alon's argument was determining
a close relation between the toughness of a regular graph and its
eigenvalues.
Independently and around the same time 1995, Brouwer found a slightly
better result relating the toughness of a regular graph to its
eigenvalues. In this talk, I will present some tight connections
between the eigenvalues of a connected regular graph and the maximum
number of edge-disjoint spanning trees in the graph that can be seen
as a spectral version of Nash-Williams/Tutte Theorem. I will show some
improvements of Brouwer's bound in certain ranges of toughness and
discuss another problem of Brouwer related to the toughness of graphs
attaining equality in the Hoffman ratio bound for the independence
number. This is joint work with my Ph.D. student, Wiseley Wong.