2nd IAMCS Workshop on Quantum Computation and Information

May 13 – 15, 2019
Texas A&M University
Blocker 149

From Abacus to Quantum Computer
(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.

Registration is free. The registration for the workshop will end on May 9.
All participants should register (even organizers and invited speakers).

If you would like to contribute a poster to this workshop, please send e-mail to Carrie Relles with the title and abstract of your poster.

Workshop Organizers

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

Preliminary Program

Monday, May 13

8:00-9:00Registration, Breakfast
9:00-10:00Graeme Smith, Monotonicity Under Local Operations: Linear Entropic Formulas
10:30-11:30Xiaodi Wu, Provable quantum advantages for optimization
1:30-2:30Pawel Wocjan, Spectral Bounds for Classical and Quantum Graph Parameters
3:00-4:00Joseph (JM) Landsberg, Quantum min-flow/max-cut and representation theory in quantum information theory
4:00-5:00Sang-Gyun Youn, Temperley-Lieb quantum channels

Tuesday, May 14

9:00-10:00Julia Plavnik, An algebraic framework for Topological Quantum Computing
10:30-11:30Lukasz Cincio, Learning Quantum Algorithms for NISQ Computers
11:30-12:15Poster session
1:30-2:30Gorjan Alagic, Unpredictable functions against quantum-superposition queries
3:00-4:00Fang Song, Basing cryptography on NP-hardness using quantum reductions
4:00-5:00Li Gao, Entanglement Breaking Time of Decoherence Semigroups
6:00-8:00Speakers' Dinner at Poppy's

Wednesday, May 15

8:00- 9:00Breakfast
9:00-10:00Andreas Klappenecker, Hybrid Quantum Codes
10:30-11:30Srinivasan Arunachalam, Quantum hardness of learning shallow classical circuits
11:30-12:30Scott Pakin, Programming a Quantum Annealer
12:30- 2:00Lunch
2:00- 5:00Discussion

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.


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.