quantum computing is receiving increasing attention as
it promises to revolutionize the current computational landscape. the
advent of quantum computers will be particularly disruptive in the
field of cryptography, where characteristically quantum properties
like entanglement and the ``no-cloning theorem'' open up a plethora of
novel opportunities. in this talk, i will describe two broad, and
connected, research questions. the first is: if a quantum device is
meant to perform tasks that are beyond the reach of classical
computers, how can a classical user trust that her quantum device is
behaving as intended? i will focus particularly on the connections of
this question with foundational questions in quantum information. the
second is: once we trust our quantum devices, what kinds of
cryptographic tasks can we realize that are beyond the reach of
classical computers? i will describe some concrete examples.

in my defense, i will talk about three relative topics relative to sparse recovery and representation of signals. i will start with the topic of recovering the low-rank matrix from incomplete measurements with prior information. signal recovery assumes that we know the sensing matrix i.e. the linear transformation. but sometimes, we want the sparse representation of signals without knowing the transformation between the signal and its representation. thus in the second topic, i'll talk about a novel algorithm that allows us to learn the linear transformation as well as the sparse representation and admits the transformation in complexity $o(n\log n)$ for a $n$ dimensional input signal. in the third topic, i'll introduce the usage of representation learning assuming that the transformation is a more complex function. i'll propose a deep neural network structure that can be used in image generation and introduce a specific application about it raised in computer game industry.

quantum computing has notable impacts on computer
science in recent years. while quantum computers are about to achieve
so-called ``quantum supremacy'' (i.e., solving some
classically-intractable computational tasks), it is the right time to
understand the capabilities and limits of quantum computers. in this
talk, i will address the following two questions: 1) what is the power
of near-term quantum computers? 2) what speedup can general quantum
computers achieve for problems in machine learning and data analysis?
we will first see that a general quantum computer is strictly more
powerful than small-depth quantum computers in the presence of
classical computers. then, i will show quantum-inspired classical
algorithms for problems including svm, low-rank linear system,
low-rank sdp, and more. our algorithms running in time polylog(n) are
asymptotically as good as existing quantum ones. this result also
implies that existing quantum machine learning algorithms have not
achieved exponential quantum speedups. finally, i will discuss
polynomial quantum speedups for fundamental problems in data analysis
and their limits under plausible assumptions in complexity theory.