Date: Friday, March 29, 2024, 9:30am-4pm
Location: Room 109, Warren Weaver Hall (NYU), 251 Mercer St, New York NY 10012
NYU Quantum Algorithms, Complexity and Cryptography (QuACC) Day is a one-day workshop bringing together researchers in the broader New York City area for a day of talks and discussion on the latest research in quantum algorithms, complexity theory, cryptography, and related topics. Anyone with an interest in quantum computing is welcome to attend.
Registration for this event is closed.
Schedule (subject to change)
9:30-10:00am Coffee and welcome
10:00am-10:45am Talk: Natalie Parham
The Quest for Quantum Circuit Lower Bounds: Implications and Future Directions
Abstract: In this talk, I introduce a method for proving quantum circuit lower bounds via the Pauli spectrum of quantum channels— which can be viewed as a quantum analogue of the Fourier spectrum of classical Boolean functions. This perspective allows us to assign a notion of degree to quantum circuits that is related to their computational complexity. We will focus on the QAC circuit class, where the gate set includes arbitrary single-qubit gates and many-qubit Toffoli gates. These many-qubit gates put QAC circuits just beyond the barriers imposed by our existing lower bound techniques, yet proving lower bounds against QAC is a longstanding challenge in quantum circuit complexity. Looking at the Pauli spectrum of QAC0 channels, I will show that when the circuit has a limited number of auxiliary qubits, the Pauli spectrum is approximately low degree. Once we have this, it is easy to prove circuit lower bounds against Boolean functions like Parity and Majority, and construct a learning algorithm. We conjecture that the results hold for all QAC0 channels, not just those with a few auxiliary inputs. Based on joint work with Shivam Nadimpalli, Francisca Vasconcelos and Henry Yuen.
11:00am-11:45am Talk: Dhrumil Patel
Wave Matrix Lindbladization as an Approach for Simulating Markovian Quantum Dynamics
Abstract: Density Matrix Exponentiation is a technique for simulating Hamiltonian dynamics when the Hamiltonian to be simulated is available as a quantum state. We present a natural analogue to this technique, called wave matrix Lindbladization, for simulating Markovian dynamics governed by the well known Lindblad master equation. In order to do so, we introduce an input model in which Lindblad operators are encoded into pure quantum states, called program states, and our technique simulates Lindbladian evolution by means of interacting the system of interest with these program states. We begin by focusing on a simple case in which the Lindbladian consists of only one Lindblad operator and a Hamiltonian. Thereafter, we extend the method to simulating general Lindbladians and other cases in which a Lindblad operator is expressed as a linear combination or a polynomial of the operators encoded into the program states. We propose quantum algorithms for all these cases and also investigate their sample complexities, i.e., the number of program states needed to simulate a given Lindbladian evolution approximately. Finally, we demonstrate that our quantum algorithms provide an efficient route for simulating Lindbladian evolution relative to the full tomography of encoded operators.
11:45am-12:00pm Sponsor presentation
12:00pm-2:00pm Lunch (on your own)
2:00pm-2:45pm Talk: Kunal Sharma
Improved techniques for quantum simulation
Abstract: Quantum simulation, a promising early application of quantum computing, offers notable advantages over classical methods. In this talk, I will focus on improved techniques for quantum simulation that leverage the structure of Hamiltonians to decrease simulation costs. I will also discuss improved error mitigation techniques for estimating the expectation value of local observables. Additionally, I will emphasize the comparative simplicity of simulating specific open quantum systems over Hamiltonian dynamics with near-term devices.
3:00pm-3:45pm Talk: Tina Zhang
Compiled nonlocal games with applications in cryptography.
Abstract: Since Bell's historical observation that some nonlocal games can be won by quantum entangled players with higher probability than by classical players, the entangled two-prover model of computation has been a model of great interest in quantum complexity theory and quantum foundations. Recently, Kalai, Lombardi, Vaikuntanathan and Yang introduced a cryptographic compilation scheme which maps any nonlocal game to a single-prover cryptographically sound argument in a way that preserves quantum completeness and classical soundness, using quantum fully homomorphic encryption (or classical-client quantum blind delegation) in order to simulate the separation between the provers. We study the quantum soundness properties of this compilation scheme, and show how it can be used to prove results in classical-client quantum delegation in a modular and unified way by combining techniques that originate in the study of self-testing with cryptographic tools.
4:00pm- Social activities
Organisers: Nick Spooner (University of Warwick/NYU) and Henry Yuen (Columbia).
Sponsor: SandboxAQ