May 13 – 15, 2019
Texas A&M University
Blocker Building, Room 149
Registration is Closed
If you would like to present a POSTER, please register by emailing Carrie Relles (carrie@stat.tamu.edu) with the following information:
- First name
- Last Name
- Affiliation
- Title and Abstract of poster
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 this 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 The Institute for Applied Mathematics and Computational Science, a College of Engineering Strategic Initiative Grant, the Department of Mathematics, and a T3 award.
Workshop Organizers:
Michael Brannan, Assistant Professor, Department of Mathematics, Texas A&M University
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
Stephan Eidenbenz, Information Science & Technology Institute Director, Los Alamos National Laboratory
Invited Speakers:
Gorjan Alagic, Assistan Research Professor, University of Maryland
Lukasz Cincio, Scientist, Los Alamos National Lab
Scott Pakin, Scientist, Los Alamos National Lab
Julia Plavnik, Charlotte Ann Griffin Assistant Professor, Indiana University, Bloomington
Graeme Smith, Assistant Professor, University of Colorado, Boulder
Pawel Wocjan, Associate Professor, University of Central Florida, Orlando
Sang-Gyun, Youn, Coleman Postdoctoral Fellow, Queen’s University, Kingston
Xiaodi Wu, Assistant Professor, University of Maryland
Srinivasan Arunachalam, Postdoctoral Researcher, MIT
Fang Song, Assistant Professor, Texas A&M University, College Station
Joseph (JM) Landsberg, Professor, Texas A&M University, College Station
Li Gao, Visiting Assistant Professor, Texas A&M University, College Station
Andreas Klappenecker, Professor, Texas A&M University, College Station
Schedule:
Monday, May 13, 2019 (Blocker 149)
8:00-9:00: Registration/Breakfast
9:00-10:00: Graeme Smith, University of Colorado
Monotonicity Under Local Operations: Linear Entopick Formulas
10:00-10:30: Break
10:30-11:30: Xiaodi Wu, University of Maryland
Provable Quantum Advantages for Optimization
11:30-12:15:Discussion
12:15-1:30: Lunch
1:30-2:30: Pawel Wocjan, University of Central Florida
Spectral Bounds for Classical and Quantum Graph Parameters
2:30-3:00: Break
3:00-4:00: JM Landsberg, Texas A&M University
Quantum Min-flow/max-cut and Representation Theory in Quantum Information Theory
4:00-5:00: Sang-Gyun Youn, Queen’s University
Temperley-Lieb Quantum Channels
Tuesday, May 14, 2019 (Blocker 149)
8:00-9:00:Registration/Breakfast
9:00-10:00: Julia Plavnik, Indiana University
An Algebraic Framework for Topological Quantum Computing
10:00-10:30: Break
10:30-11:30: Lukasz Cincio, Los Alamos National Lab
Learning Quantum Algorithms for NISQ Computers
11:30-12:15: Poster Session
12:15-1:30: Lunch
1:30-2:30: Gorjan Alagic, University of Maryland
Unpredictable Functions Against Quantum-Superposition Queries
2:30-3:00: Break
3:00-4:00: Fang Song, Texas A&M University
Basing Cryptography on NP-Hardness Using Quantum Reductions
4:00-5:00: Li Gao, Texas A&M University
Entanglement Breaking Time of Decoherence Semigroup
6:00-8:00: Dinner @ Poppy’s (Speakers only)
Wednesday, May 15, 2019 (Blocker 149)
8:00-9:00: Registration/Breakfast
9:00-10:00: Andreas Klappenecker, Texas A&M University
Hybrid Quantum Codes
10:00-10:30: Break
10:30-11:30: Srinivasan Arunachalam, MIT
Quantum Hardness of Learning Shallow Classical Circuits
11:30-12:30: Scott Pakin, Los Alamos National Lab
TBA
12:30-2:00: Lunch
2:00-5:00: Discussion
Invited Talks:
Unpredictable Functions against Quantum-Superposition Queries
*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.
Quantum Hardness of Learning Shallow Classical Circuits
*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)
Learning Quantum Algorithms for NISQ Computers
*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.
Entanglement Breaking Time of Decoherence Semigroups
*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.
Hybrid Quantum Codes
*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.
Quantum min-flow/max-cut and representation theory in quantum information theory.
*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
Programming a Quantum Annealer
*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.
An algebraic framework for Topological Quantum Computing
*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.
Monotonicity Under Local Operations: Linear Entropic Formulas
*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
Basing Cryptography on NP-hardness using Quantum Reductions
*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
Spectral Bounds for Classical and Quantum Graph Parameters
*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.
Provable Quantum Advantages for Optimization
*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).
Temperley-Lieb Quantum Channels
*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.
Posters:
Quantum Security Properties of Hash Functions
Benjamin Hamlin, TAMU
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.
Bounds for Hybrid Codes
Andrew Nemec, TAMU
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.
An Expository on Peter Shor’s Quantum Algorithm for Factoring
Kristopher Watkins, TAMU
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.
Delegating Quantum Computation Using Only Hash Functions
Jiayu Zhang, Boston University
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.
Braid Group Representations from Twisted Tensor Products of Group Algebras
Qing Zhang, TAMU
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.