Friday, 1 November
9 AM - 5 PM
Room 4102 (Science Center), Graduate Center CUNY
9:30 AM
The Hardness of Learning Random Quantum Circuits and its Cryptographic Applications
Henry Yuen
Columbia University
In classical computer science, the theory of machine learning and the theory of cryptography are really two sides of the same coin. Cryptosystems can be broken by nontrivial learning algorithms, and conversely computationally hard learning problems can serve as the basis for secure cryptography. Does the same tight-knit correspondence hold in the quantum world? Recently, both quantum learning theory and quantum cryptography have seen a flurry of new models, new algorithms, new protocols, and many new questions.
In this talk I will connect these two developments. In particular, I will discuss some well-motivated hardness assumptions about the learning and cloning of outputs of random quantum circuits, and how these assumptions yield secure forms of quantum cryptography. Remarkably, the security of these cryptographic primitives appear to rely on fewer mathematical assumptions than is required for any classical cryptosystem. I will discuss a quantum digital signature scheme that is (in principle) NISQ friendly: it can be implemented on a noisy quantum computer, but still remains secure against adversaries with noiseless quantum computers.This opens the door to the intriguing possibility of having a near-term experimental proposal of quantum cryptographic advantage.
No background in quantum learning theory or quantum cryptography will be assumed. Based on joint work with Bill Fefferman, Soumik Ghosh, and Makrand Sinha.
10:45 AM
Quantum Relaxation for Combinatorial Optimization
Rudy Raymond
JP Morgan Chase
Many quantum algorithms for hard combinatorial optimization problems rely on finding the ground state of a diagonal Hamiltonian which gives the binary variables of the optimal solution. Meanwhile, relaxing binary variables to continuous ones, e.g., relaxation in the Linear Programming (LP), is a typical strategy in classical algorithms to solve hard combinatorial optimization problems. In this talk, I will introduce a quantum-relaxation based optimizer called Quantum Random Access Optimization (QRAO) that relies on finding the ground state of non-diagonal Hamiltonian. QRAO is based on the quantum information primitive called Quantum Random Access Codes (QRACs) to encode more variables per qubit. I will give some theoretical results of QRAO and recent experimental results showing QRAO can outperform the best-known quantum methods and is comparable with the best classical solvers on MaxCut problems of standard benchmark graphs with several hundred nodes.
12 PM -1 PM
LUNCH
1:00 PM
Qubits without qubits: field-based photonic quantum computing
Olivier Pfister
University of Virginia
I will describe our progress toward making a qumode-based, ie. field-based, quantum computer using only light. This approach is motivated by its unique scalability potential, based on the physics of the optical frequency comb, which leverages the spectral and temporal degrees of freedom. I will also describe how recent progress in photon-number-resolving detection technology enables viable fault-tolerant quantum architectures for photonic quantum computers.
2:00 PM
Efficient Learning of quantum state
Nengkun Yu
Stony Brook University
Testing the properties of unknown quantum states is fundamental to understanding quantum devices. For a general unknown state, an exponential number of copies is needed. In the low complexity region, we establish the connection between the state's complexity—i.e., the time required to generate this state—and the sample complexity of learning it. Furthermore, we show that one can learn nontrivial information from a single copy if the state has low complexity.
3:30 PM
Uncloneable Quantum Cryptography and Quantum Proofs
Supartha Podder
Stony Brook University
Quantum cryptography is known for enabling functionalities that are unattainable using classical information alone. The quantum no-cloning principle tells us that, in a certain sense, quantum information behaves more like a physical object than a digital one: there are situations where quantum information can be distributed and used, but it cannot be duplicated. This property gave rise to a fascinating subfield of quantum cryptography known as uncloneable cryptography. In this talk, we will explore uncloneable cryptography and its relation with quantum proofs.
ORGANIZER
Mark Hillery (Hunter college/ GC-CUNY)