May 13 – 15, 2019
Texas A&M University
Blocker 149
(Image courtesy of Zhengang Wang)
The interdisciplinary science of quantum computation has seen rapid development over the last 25 years, encouraged by fundamental progress in computer science, mathematics and physics. Several disparate computation schemes have emerged, including the quantum circuit model, topological quantum computers and quantum annealing machines, contributing to the astonishing breadth of research disciplines with applications to quantum information science.
This workshop will bring together researchers in quantum information science from physics, computer science and mathematics to provide an overview of the field to interested scientists, discuss the current state of the science, and inspire the next generation of researchers to pursue this topic.
The three-day program features thirteen invited talks and a poster session.
The workshop is supported in part by IAMCS, a College of Engineering Strategic Initiative Grant, the Department of Mathematics, and a T3 award.
Michael Brannan, Assistant Professor, Department of Mathematics, Texas A&M University
Stephan Eidenbenz, Information Science & Technology Institute Director, Los Alamos National Lab
Andreas Klappenecker, Professor, Department of Computer Science & Engineering, Texas A&M University
Eric Rowell, Professor, Department of Mathematics, Texas A&M University
Fang Song, Assistant Professor, Department of Computer Science & Engineering, Texas A&M University
| 8:00-9:00 | Registration, Breakfast |
| 9:00-10:00 | Graeme Smith, Monotonicity Under Local Operations: Linear Entropic Formulas |
| 10:00-10:30 | Coffee |
| 10:30-11:30 | Xiaodi Wu, Provable quantum advantages for optimization |
| 11:30-12:15 | Discussion |
| 12:15-1:30 | Lunch |
| 1:30-2:30 | Pawel Wocjan, Spectral Bounds for Classical and Quantum Graph Parameters |
| 2:30-3:00 | Coffee |
| 3:00-4:00 | Joseph (JM) Landsberg, Quantum min-flow/max-cut and representation theory in quantum information theory |
| 4:00-5:00 | Sang-Gyun Youn, Temperley-Lieb quantum channels |
| 8:00-9:00 | Breakfast |
| 9:00-10:00 | Julia Plavnik, An algebraic framework for Topological Quantum Computing |
| 10:00-10:30 | Coffee |
| 10:30-11:30 | Lukasz Cincio, Learning Quantum Algorithms for NISQ Computers |
| 11:30-12:15 | Poster session |
| 12:15-1:30 | Lunch |
| 1:30-2:30 | Gorjan Alagic, Unpredictable functions against quantum-superposition queries |
| 2:30-3:00 | Coffee |
| 3:00-4:00 | Fang Song, Basing cryptography on NP-hardness using quantum reductions |
| 4:00-5:00 | Li Gao, Entanglement Breaking Time of Decoherence Semigroups |
| 6:00-8:00 | Speakers' Dinner at Poppy's |
| 8:00- 9:00 | Breakfast |
| 9:00-10:00 | Andreas Klappenecker, Hybrid Quantum Codes |
| 10:00-10:30 | Coffee |
| 10:30-11:30 | Srinivasan Arunachalam, Quantum hardness of learning shallow classical circuits |
| 11:30-12:30 | Scott Pakin, Programming a Quantum Annealer |
| 12:30- 2:00 | Lunch |
| 2:00- 5:00 | Discussion |
*Gorjan Alagic, Assistant Research
Professor, University of Maryland
Unpredictability is a fundamental concept in pseudorandomness and
cryptography. Classically, a function is unpredictable if no query
algorithm can predict the function’s values on unqueried inputs. In
the quantum setting, however, algorithms can query in superposition;
as a result, there is no notion of “unqueried input.” Given this
fundamental obstacle, how do we define unpredictability against
quantum queries? Providing a convincing answer to this question has
proved elusive. In this talk, I will discuss this problem and some
approaches to solving it. I will show that a previous approach of
Boneh and Zhandry suffers from a fatal flaw: I will describe an
evidently predictable function which satisfies their definition of
unpredictability. I will then discuss a new notion, called
“blind-unforgeability” and show that it fulfills a wide range of
desired criteria. I will also discuss connections to cryptography,
quantum query complexity, and more.
*Srinivasan Arunachalam, Postdoc, MIT
In this paper we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of PAC learning. In order to attain our results, we establish connections between quantum learning, pseudo-random functions and quantum-secure cryptosystems. Using this connection, we show the hardness of learning AC0 and TC0 (under the uniform distribution) and the PAC hardness of learning depth-2 TC0 circuits, assuming the Learning with Errors problem is hard to solve on a quantum computer. This gives a strong conditional negative answer to one of the "Ten Semi-Grand Challenges for Quantum Computing Theory" raised by Aaronson [Aar05], who asked if AC0 and TC0 can be PAC-learned in quantum polynomial time.
Joint work with Alex B. Grilo and Aarthi Sundaram (available at arXiv:1903.02840)
*Lukasz Cincio, Scientist, Los Alamos
National Lab
Short-depth algorithms are crucial for reducing computational
error on near-term quantum computers, for which decoherence and gate
infidelity remain important issues. Here we present a machine-learning
approach for discovering such algorithms. We apply our method to a
ubiquitous primitive: computing the overlap between two quantum
states. The standard algorithm for this task, known as the Swap Test,
is used in many applications such as quantum support vector
machines. Here, our machine-learning approach finds algorithms that
have shorter depths than the Swap Test, including one that has a
constant depth (independent of problem size). Taking this as
inspiration, we also present a novel constant-depth algorithm for
computing the integer Renyi entropies where our circuit depth is
independent of both the number of qubits as well as the Renyi
index. These integer Renyi entropies are useful, e.g., for computing
the entanglement spectrum for condensed matter applications. Finally,
we demonstrate that both our state overlap algorithm and our Renyi
entropy algorithm have increased robustness to noise relative to their
state-of-the-art counterparts in the literature.
*Li Gao, Visiting Assistant Professor,
Texas A&M University, College Station
A big challenge in the practical realization of quantum computers
is decoherence. When a quantum system loses coherence, it becomes like
a classical system and no actual quantum computation can be
performed. A decoherence process is also entanglement breaking,
because a classical system can share no entanglement with others. In
this talk, I will present an estimate of the entanglement breaking
time for decoherence semigroups that is independent of the dimension
of auxiliary system.
This talk is based on joint work with Marius Junge and Nicholas LaRacuente.
*Andreas Klappenecker, Professor,
Texas A&M University, College Station
A hybrid code can simultaneously encode classical and quantum information into quantum digits such that the information is protected against errors when transmitted through a quantum channel. We give an introduction to hybrid quantum codes. Among other things, we show that a hybrid code can detect more errors than a comparable quantum code encoding the classical and quantum information.
This is joint work with Andrew Nemec.
*Joseph (JM) Landsberg, Professor,
Texas A&M University, College Station
I will illustrate the use of representation theory (that is, the exploitation of symmetry in linear algebra) in quantum information theory by presenting numerous counter-examples to the Quantum min-flow/max cut conjectures.
This is joint work with F. Gesmundo and M. Walter
*Scott Pakin, Scientist,
Los Alamos National Lab
A quantum annealer is a special-purpose quantum computer that
exploits quantum effects to approximate the solution to a
particular NP-hard problem: minimizing a 2-local Ising-model
Hamiltonian function. Essentially, one can think of this as
simulated annealing performed in hardware. Quantum annealers
containing thousands of qubits (quantum bits) are already
commercially available, representing orders of magnitude more
qubits than what is provided by any current general-purpose
quantum computer.
A timely research challenge -- and the subject of this talk -- is
how to effectively program a quantum annealer. At the lowest
level, a quantum-annealing program is merely a list of
coefficients of a quadratic pseudo-Boolean function.
Virtually all quantum-annealing programs written to date
required painstaking manual effort to map problems to
Hamiltonian coefficients. In this talk we demonstrate how to
map arbitrary programs written in a classical programming
language into a minimization problem. We argue that with
this approach, efficient approximate solutions to difficult
(i.e., NP) problems can in fact be *easier* to express than
with conventional, classical techniques.
*Julia Plavnik, Charlotte Ann Griffin Assistant Professor,
Indiana University, Bloomington
In the last years, the possibility of constructing a quantum
computer has gotten a lot of attention. There are different models and
perspectives about it, one of them has a topological nature which has
the advantage to be protected against decoherence. In this talk, we
will introduce the notion of a modular tensor category, which is a
rich mathematical structure that models 2-dimensional topological
phases of matter, which are a route to topological quantum
computation. To get a better understanding of these categories, we
will present some important examples and properties. Then, we will
focus on the mathematical formulation of the gauging procedure, which
is a way to construct new modular tensor, and some open questions
related to this. If time allows, we will also discuss some new
directions, in particular, some results about super-modular
categories, which are some pre-modular categories with a distinguished
fermion on them.
*Graeme Smith, Assistant Professor,
University of Colorado, Boulder All correlation measures, classical and quantum, must be monotonic under local operations. In this paper, we characterize monotonic formulas that are linear combinations of the von Neumann entropies associated with the quantum state of a physical system which has n parts. We show that these formulas form a polyhedral convex cone, which we call the monotonicity cone, and enumerate its facets. We illustrate its structure and prove that it is equivalent to the cone of monotonic formulas implied by strong subadditivity. We explicitly compute its extremal rays for n up to 5. We also consider the symmetric monotonicity cone, in which the formulas are required to be invariant under subsystem permutations. We describe this cone fully for all n. In addition, we show that these results hold even when states and operations are constrained to be classical.
Joint work with Mohammad Alhejji
*Fang Song, Assistant Professor,
Texas A&M University, College Station
A fundamental pursuit in complexity theory concerns reducing
worst-case problems to average-case problems. There exist complexity
classes such as PSPACE that admit worst-case to average-case
reductions. Many other classes such as NP, however, the evidence so
far is typically negative, in the sense that the existence of such
reductions would cause collapses of the polynomial hierarchy. Basing
cryptography, e.g., the average-case hardness of inverting one-way
permutations, on NP-completeness is a particularly intriguing
instance. We initiate a study of the quantum analogues of these
questions and show that if NP-complete problems reduce to inverting
one-way permutations using certain types of quantum reductions, then
coNP is a subset of QIP(2).
Joint work with Nai-Hui Chia and Sean Hallgren. arXiv:1804.10309
*Pawel Wocjan, Associate Professor,
University of Central Florida, Orlando
Spectral graph theory is a well-established branch of graph theory
and studies the properties of a graph with the help of eigenvalues and
eigenvectors of matrices associated to graphs such as its adjacency
and Laplacian matrices. One of the most well-known results in spectral
graph theory is the so-called Hoffman lower bound on the chromatic
number a graph in terms of the maximal and minimal eigenvalues of its
adjacency matrix.
Recently, researchers in quantum information theory have been begun
to study operator-valued relaxations of classical graph
parameters. For instance, instead of assigning colors to vertices that
must be different whenever the vertices are adjacent, a quantum
coloring is a collection of orthogonal projectors to vertices that
must satisfy certain completeness and orthogonality relations.
In this talk, I will describe how to extend spectral graph theory
to obtain new lower and upper bounds on classical and quantum graph
parameters.
This is based on joint work with Clive Elphick.
*Xiaodi Wu, Assistant Professor,
University of Maryland, College Park
Recent developments in quantum computation, especially in the emerging
topic of “quantum machine learning”, suggest that quantum algorithms
might offer significant speed-ups for optimization and machine
learning problems. In this talk, I will describe three recent
developments on provable quantum advantages for optimization and
machine learning from our group.
(1) The first one optimizes a general (dimension n) convex function
over a convex body using O(n) quantum queries to oracles that evaluate
the objective function and determine membership in the convex body;
this gives a quadratic improvement over the best-known classical
algorithm.
(2) The second one solves a special class of convex optimization
problems, semidefinite programs (SDPs), where we design a quantum
algorithm that solves n-dimensional SDPs with m constraints in
O(n1/2 + m1/2), whereas the state-of-the-art classical
algorithms run in time at least linear in n and m.
(3) The third one is a sublinear quantum algorithm for training
linear and kernel-based classifiers that runs in O(n1/2+
d1/2) given n data points in Rd, whereas the
state-of-the-art (and optimal) classical algorithm runs in O(n +d).
Based on results in arXiv:1809.01731v1 (QIP 2019), arXiv:1710.02581v2 (QIP 2019), and arXiv: 1904.02276 (ICML 2019).
*Sang-Gyun Youn, Coleman Postdoctoral
Fellow, Queen's University, Kingston
A new class of quantum channels, which we call Temperley-Lieb channels, and their investigated properties will be discussed in this talk. It has turned out that some important quantum information-theoretic quantities of these channels are computable despite their highly non-trivial structures. As an effort to explain their quantitative aspects, asymptotically sharp minimum output entropy, Holevo capacity, one-shot quantum capacity and entanglement of formation will be presented.
In this work, we consider security properties of cryptographic hash
functions versus quantum adversaries. We adapt the seven properties
from Rogaway and Shrimpton (FSE'04) to a quantum setting, and prove
that allowing the adversary superposition access to the challenger
provides no additional power over classical access, showing that
superposition attacks are not useful in this setting. We confirm that
the implications and separations among the adapted classical
properties carry over to a quantum setting. Moreover, we consider an
inherently quantum property called collapsing, proposed by Unruh
(Eurocrypt'16), and construct explicit examples separating it from
several classical properties. Finally, we examine the
property-preservation of several iterated hashing schemes and show, in
particular, that that the ROX construction in Andreeva et
al. (Asiacrypt'07) preserves the seven properties as well as
collapsing in the quantum random oracle model.
Hybrid codes simultaneously encode classical and quantum
information. We give weight enumerators for general hybrid codes and
derive linear programming bounds from them. These bounds are compared
to bounds for quantum codes to identify parameters where hybrid codes
may outperform quantum codes.
Peter Shor gave us the beautiful algorithm for factoring a number
in polynomial time of the size of the number. This is a huge threat to
RSA encryption and we can also apply some of the methods to solving
the Discrete Logarithm Problem in polynomial time as well. I have
mixed Shor's ideas as well as a few others to provide a simple
overview of how we beat the factoring problem.
In this paper, we construct a new scheme for delegating a large
circuit family, which we call "C+P circuits". "C+P" circuits are the
circuits composed of Toffoli gates and diagonal gates. Our scheme is
non-interactive, only requires small quantum resources on the client
side, and can be proved secure in the quantum random oracle model,
without relying on additional assumptions, for example, the existence
of fully homomorphic encryption. In practice the random oracle can be
replaced by appropriate hash functions or symmetric key encryption
schemes, for example, SHA-3, AES.
This protocol allows a client to delegate the most expensive part
of some quantum algorithms, for example, Shor's algorithm. The
previous protocols that are powerful enough to delegate Shor's
algorithm require either many rounds of interactions or the existence
of FHE. The quantum resources required by the client are fewer than
when it runs Shor's algorithm locally. Different from many previous
protocols, our scheme is not based on quantum one time pad, but on a
new encoding called "entanglement encoding". We then generalize the
garbled circuit to reversible garbled circuit to allow the computation
on this encoding.
To prove the security of this protocol, we study key dependent
message (KDM) security in the quantum random oracle model. Then as a
natural generalization, we define and study quantum KDM security. KDM
security was not previously studied in quantum settings.
In a topological quantum computer, braiding anyons corresponds to
computation in unitary braid group representations on their state
space. These braid group representations arise in a complicated way
from centralizer algebras for simple objects in tensor categories. It
is an important problem to find more straightforward descriptions of
these braid group representations. Towards this goal, we are working
on a method of constructing braid group representations from twisted
tensor products of group algebras. We outline this construction, give
examples, and compare the resulting representations with the ones
coming from tensor categories.
This is joint work with Paul Gustafson,
Andrew Kimball and Eric Rowell.
Quantum Hardness of Learning Shallow Classical Circuits
Learning Quantum Algorithms for NISQ Computers
Entanglement Breaking Time of Decoherence Semigroups
Hybrid Quantum Codes
Quantum min-flow/max-cut and representation theory in quantum
information theory.
Programming a Quantum Annealer
An algebraic framework for Topological Quantum Computing
Monotonicity Under Local Operations: Linear Entropic Formulas
Basing Cryptography on NP-hardness using Quantum Reductions
Spectral Bounds for Classical and Quantum Graph Parameters
Provable Quantum Advantages for Optimization
Temperley-Lieb Quantum Channels
Posters
Quantum Security Properties of Hash Functions
Benjamin Hamlin, TAMU
Bounds for Hybrid Codes
Andrew Nemec, TAMU
An Expository on Peter Shor's Quantum Algorithm for Factoring
Kristopher Watkins, TAMU
Delegating Quantum Computation Using Only Hash Functions
Jiayu Zhang, Boston University
Braid Group Representations from Twisted Tensor Products of Group Algebras
Qing Zhang, TAMU