### Wednesday, February 3rd

All times are in Central European Time (CET). Underlined authors are presenting the talks.
Click on the talk title to access the recording.

Sessions on Wednesday are sponsored by Baidu.

### Monday | Tuesday | Thursday | Friday

##### 08:30 - 10:30 | Poster Session C

Posters in Rooms C.1 to C.4 are presenting. Visit the 3D poster rooms and use the "Video chat" button under each poster to engage with the poster representative during this time. This is linked to their poster in MeetAnyway, therefore access is possible from either platform.

### Industry Session

Main stage (A)

##### 10:30 - 11:00 | Quantum Computing at Baidu

Speaker: Runyao Duan, Director of Institute for Quantum Computing, Baidu Research

Abstract

Abstract

Quantum computing is believed to be the heart of the next-generation computing technology. Our mission at Baidu Research is to be a world-class Quantum Artificial Intelligence (AI) research strength, and to continuously integrate relevant quantum technologies into Baidu's core business. We have general interests in Quantum Information Science with three research priority topics: Quantum AI, Quantum Algorithm, and Quantum Architecture - altogether form the QAAA research plan. As a result of this plan, we develop the Baidu Quantum Platform (BQP), which currently contains three essential products: 1) Quantum Leaf, a cloud-native quantum computing platform; 2) Paddle Quantum, a quantum machine learning toolkit developed based on Baidu's deep learning platform PaddlePaddle; 3) Quanlse, a cloud-based platform for quantum control. With the help of BQP and its further development, we strive to explore more possibilities of quantum technology, to build a sustainable quantum ecosystem, and finally to achieve our vision that "Everyone Can Quantum".

##### 11:00 - 11:30 | Co-designing quantum computers at IQM

Speaker: Bruno Taketani, IQM

Abstract

Abstract
Quantum computers are set to revolutionise many fields. However, a full-fledged quantum computer is still a long term goal. IQM is invested in reaching quantum advantage faster via application specific, co-design quantum computers. In this talk, we will present recent updates on the technological development at IQM Quantum Computers in developing scalable superconducting quantum processors. We will discuss our implementation of digital-analog quantum algorithms as a promising route to improve circuit depth. On the broader scope, we will also present our latest results in qubit and quantum processor development.

##### 11:30 - 12:00 | Application of quantum computing in the increasingly complex automotive value chain

Speaker: Dr. Johannes Klepsch, Product Owner Quantum Computing, BMW AG

Abstract

Abstract
The complexity is increasing rapidly in many areas of the automotive industry. The design of an automobile involves many different engineering disciplines and various tradeoffs. The vehicle software and hardware system comprise millions of lines of code. Complex processes, such as manufacturing, logistics, distribution and sales, need to be handled. In all these domains, myriads of optimization problems arise. Quantum computing-based optimization approaches promise to overcome some of the inherent scalability limitations of classical systems. This presentation investigates quantum computing applications across the automotive value chain and evaluates their suitability for quantum-based methods.

##### 12:00 - 12:30 | Round tables with Runyao Duan, Bruno Taketan, and Johannes Klepsch

At the end of the session, you can meet with the speakers directly. Round tables take place in parallel, each speaker having their own meeting.

### Diversity

Main stage (A)

##### 12:30 - 13:30 | How to promote social justice in academia

Speaker: Havi Carel, University of Bristol
Moderators: Juani Bermejo-Vega and Barbara Tautz

This talk will provide an introduction and training to participants on equality, diversity and inclusion in academia, including microaggressions and implicit bias. We will learn about the processes and factors that are barriers to equality, diversity and inclusion and discuss some ways of mitigating these in the context of academia.

##### 13:30 - 14:00 | Mingling

One on one networking session - a great way to meet new people, old friends, and make valuable connections. Participants get randomly matched for one on one talks for 3 minutes. You can try it at the 2D conference space (MeetAnyway).

##### 14:00 - 14:30 | Networking

Find out who else is here and discuss via video chat in a casual atmosphere different topics. Today's themes includes "Family & Academia" as well as some special ones, named after the winning teams of the Quantum Quiz yesterday. You can join and leave tables as you wish.

##### 14:30 on QIP TV | Lab tour "Quantum Magneto-Optics" with Viviana Villafañe

Join the QIP TV stage for an insight of the work done by the Photonic Quantum Engineering group at the Walter Schottky Institute - TU München in Garching near Munich.

### Session 2A

Main stage (A)

Authors: Anurag Anshu and Chinmay Nirkhe

Abstract

Affiliations: University of California, Berkeley | University of California, Berkeley

Extended abstract

Abstract
The No Low-energy Trivial States (NLTS) conjecture of Freedman and Hastings (Quantum Information and Computation, 2014) -- which posits the existence of a local Hamiltonian with a super-constant circuit lower bound on the complexity of all low-energy states -- identifies a fundamental obstacle to the resolution of the quantum PCP conjecture. In this work, we provide new techniques based on entropic and local indistinguishability arguments that prove circuit lower bounds for all the low-energy states of local Hamiltonians arising from quantum error-correcting codes. For local Hamiltonians arising from nearly linear-rate and polynomial-distance LDPC stabilizer codes, we prove super-constant circuit lower bounds for the complexity of all states of energy o(n) (which can be viewed as an almost linear NLTS theorem). Such codes are known to exist and are not necessarily locally-testable, a property previously suspected to be essential for the NLTS conjecture. Curiously, such codes can also be constructed on a two-dimensional lattice, showing that low-depth states cannot accurately approximate the ground-energy in physically relevant systems.

15:30 - 16:00 | Quantum Learning Algorithms Imply Circuit Lower Bounds

Authors: Srinivasan Arunachalam, Alex B. Grilo, Tom Gur, Igor C. Oliveira and Aarthi Sundaram

Abstract

Affiliations: IBM T. J. Watson Research Center | Sorbonne Universite, CNRS, LIP6 | University of Warwick | University of Warwick | Microsoft Quantum

Abstract
We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Specifically, let C be a class of polynomial-size concepts, and suppose that C can be learned in the PAC model under the uniform distribution with membership queries, and with error 1/2 - c by a time T quantum algorithm. We prove that if (c^2 * T) << 2^n/n, then BQE is not contained in C, where BQE = BQTIME[2^{O(n)}] is an exponential-time analogue of BQP. This result is optimal in both c and T since it is not hard to learn any class C of functions in (classical) time T = 2^n (with no error) or in quantum time T = poly(n) with error at most 1/2 - \Omega(2^{-n/2}) via Fourier sampling. In other words, even a marginal improvement on these generic learning algorithms would lead to major consequences in complexity theory. Our proof builds on several works in learning theory, pseudorandomness, and computational complexity, and crucially, on a connection between non-trivial classical learning algorithms and circuit lower bounds established by Oliveira and Santhanam (CCC 2017). Extending their approach to quantum learning algorithms turns out to create significant challenges. To achieve that, we show among other results how pseudorandom generators imply learning-to-lower-bound connections in a generic fashion, construct the first conditional pseudorandom generator secure against uniform quantum computations, and extend the local list-decoding algorithm of Impagliazzo, Jaiswal, Kabanets and Wigderson (SICOMP 2010) to quantum circuits via a delicate analysis. We believe that these contributions are of independent interest and might find other applications.

16:00 - 16:30
Quantum Algorithmic Measurement

Authors: Dorit Aharonov, Jordan Cotler and Xiao-Liang Qi

Abstract

Affiliations: The Hebrew University of Jerusalem | Harvard University | Stanford University

Extended abstract

Abstract
Can quantum computational tools enhance the precision and efficiency of physical experiments? Promising examples are known, but a systematic treatment and comprehensive framework are missing. We introduce Quantum Algorithmic Measurements (QUALMs) to enable the study of quantum measurements and experiments from the perspective of computational complexity and communication complexity. The measurement process is described, in its utmost generality, by a many-round quantum interaction protocol between the experimental system and a full-fledged quantum computer. The QUALM complexity is quantified by the number of elementary operations performed by the quantum computer, including its coupling to the experimental system. We study how the QUALM complexity depends on the type of allowed access the quantum computer has to the experimental system: local-local, incoherent, coherent, adaptive, etc. We provide the first example of a measurement "task" for which the coherent QUALM complexity is exponentially better than the incoherent one, even if the latter is adaptive; this implies that using entanglement between different systems in experiments may lead to exponential savings in resources. We extend our results to derive a similar exponential advantage for a physically motivated measurement task which determines the symmetry class of the time evolution operator for a quantum many-body system. Many open questions are raised towards better understanding how quantum computational tools can be applied in experimental physics. A major question is whether an exponential advantage in QUALM complexity can be achieved in the NISQ era; an equally important one is to design new, efficient quantum algorithmic measurements based on our framework, perhaps relying on ideas from quantum algorithms.

16:30 - 17:00 | Round tables with Chinmay Nirkhe, Tom Gur, and Jordan Cotler
At the end of the session, you can meet with the speakers directly. Round tables take place in parallel, each speaker having their own meeting.

### Session 2B

Stage B

15:00 - 15:30 | Device-independent protocols from computational assumptions

Authors: Tony Metger, Yfke Dulek, Andrea Coladangelo, Rotem Arnon-Friedman and Thomas Vidick

Abstract

Affiliations: ETH Zurich | QuSoft, University of Amsterdam | UC Berkeley | Weizmann Institute of Science | Caltech

Extended abstract

Abstract
Device-independent protocols use untrusted quantum devices to achieve a cryptographic task. Such protocols are typically based on Bell inequalities and require the assumption that the quantum device is composed of separated non-communicating components. In this submission, we present protocols for self-testing and device-independent quantum key distribution (DIQKD) that are secure even if the components of the quantum device can exchange arbitrary quantum communication. Instead, we assume that the device cannot break a standard post-quantum cryptographic assumption. Importantly, the computational assumption only needs to hold during the protocol execution and only applies to the (adversarially prepared) device in possession of the (classical) user, while the adversary herself remains unbounded. The output of the protocol, e.g. secret keys in the case of DIQKD, is information-theoretically secure. For our self-testing protocol, we build on a recently introduced cryptographic tool (Brakerski et al., FOCS 2018; Mahadev, FOCS 2018) to show that a classical user can enforce a bipartite structure on the Hilbert space of a black-box quantum device, and certify that the device has prepared and measured a state that is entangled with respect to this bipartite structure. Using our self-testing protocol as a building block, we construct a protocol for DIQKD that leverages the computational assumption to produce information-theoretically secure keys. The security proof of our DIQKD protocol uses the self-testing theorem in a black-box way. Our self-testing theorem thus also serves as a first step towards a more general translation procedure for standard device-independent protocols to the setting of computationally bounded (but freely communicating) devices.

Authors: Srijita Kundu and Ernest Y.-Z. Tan // Anne Broadbent and Rabib Islam

Abstract

Affiliations: National University of Singapore | ETH Zurich // University of Ottawa | University of Ottawa

Abstract
We study the task of encryption with certified deletion (ECD) introduced by Broadbent and Islam (2019), but in a device-independent setting: we show that it is possible to achieve this task even when the honest parties do not trust their quantum devices. Moreover, we define security for the ECD task in a composable manner and show that our ECD protocol achieves composable security. Our protocol is based on device-independent quantum key distribution (DIQKD), and in particular the parallel DIQKD protocol based on the magic square non-local game, given by Jain, Miller and Shi (2017). To achieve certified deletion, we use a property of the magic square game observed by Fu and Miller (2017), namely that a two-round variant of the game can be used to certify deletion of a single random bit. In order to achieve certified deletion security for arbitrarily long messages from this property, we prove a parallel repetition theorem for two-round non-local games, which may be of independent interest. // Given a ciphertext, is it possible to prove the deletion of the underlying plaintext? Since classical ciphertexts can be copied, clearly such a feat is impossible using classical information alone. In stark contrast to this, we show that quantum encodings enable certified deletion. More precisely, we show that it is possible to encrypt classical data into a quantum ciphertext such that the recipient of the ciphertext can produce a classical string which proves to the originator that the recipient has relinquished any chance of recovering the plaintext should the decryption key be revealed. Our scheme is feasible with current quantum technology: the honest parties only require quantum devices for single-qubit preparation and measurements; the scheme is also robust against noise in these devices. Furthermore, we provide an analysis that is suitable in the finite-key regime.

Authors: Andrea Coladangelo, Christian Majenz and Alexander Poremba // Anne Broadbent, Stacey Jeffery, Sébastien Lord, Supartha Podder and Aarthi Sundaram

Abstract

Affiliations: UC Berkeley | CWI and QuSoft | Caltech // University of Ottawa | QuSoft and CWI | University of Ottawa | University of Ottawa | Microsoft Quantum

Abstract
Copy-protection allows a software distributor to encode a program in such a way that it can be evaluated on any input, yet it cannot be pirated'' -- a notion that is impossible to achieve in a classical setting. Aaronson (CCC 2009) initiated the formal study of quantum copy-protection schemes, and speculated that quantum cryptography could offer a solution to the problem thanks to the quantum no-cloning theorem. In this work, we introduce a quantum copy-protection scheme for a large class of evasive functions known as compute-and-compare programs'' -- a more expressive generalization of point functions. A compute-and-compare program CC[f,y] is specified by a function f and a string y within its range: on input x, CC[f,y] outputs 1, if f(x) = y, and 0 otherwise. We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM), which makes it the first copy-protection scheme to enjoy any level of provable security in a standard cryptographic model. As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called secure software leasing'', introduced very recently by Ananth and La Placa (eprint 2020), with a standard security bound in the QROM, i.e. guaranteeing negligible adversarial advantage. // Quantum cryptography is known for enabling functionalities that are unattainable using classical information alone. Recently, Secure Software Leasing (SSL) has emerged as one of these areas of interest. Given a target circuit C from a circuit class, SSL produces an encoding of C which enables the evaluation of C, and also enables a verify procedure, by which the originator of the software becomes convinced that the software is returned --- meaning that the recipient has relinquished the possibility of any further use of the software. Clearly, such functionality is unachievable using classical information alone, since it is impossible to prevent a user from keeping a copy of the software. Recent results have shown the achievability of SSL using quantum information for a class of functions called compute-and-compare (these are a generalization of the well-known point functions). These prior works, however, all make use of setup or computational assumptions. Here, we show that SSL is achievable for compute-and-compare circuits without any assumptions. Our technique is a generic reduction from any quantum message authentication code to such an SSL scheme. Along the way, we also show that point functions can be copy-protected without any assumptions, for a security definition that involves one honest and one malicious evaluator.

16:30 - 17:00 | Round tables with Tony Metger, Ernest Y.-Z. Tan, Rabib Islam, Alexander Poremba, and Sébastien Lord
At the end of the session, you can meet with the speakers directly. Round tables take place in parallel, each speaker having their own meeting.

### Session 2C

Stage C

Authors: Abhinav Deshpande, Alexey Gorshkov and Bill Fefferman

Abstract

Affiliations: QuICS/JQI/University of Maryland | Joint Quantum Institute (JQI) | University of Chicago

Extended abstract

Abstract
The field of quantum Hamiltonian complexity lies at the intersection of quantum many-body physics and computational complexity theory, with deep implications to both fields. The main object of study is the LocalHamiltonian problem, which is concerned with estimating the ground-state energy of a local Hamiltonian and is complete for the class QMA, a quantum generalization of the class NP. A major challenge in the field is to understand the complexity of the LocalHamiltonian problem in more physically natural parameter regimes. One crucial parameter in understanding the ground space of any Hamiltonian in many-body physics is the spectral gap, which is the difference between the smallest two eigenvalues. Despite its importance in quantum many-body physics, the role played by the spectral gap in the complexity of the LocalHamiltonian is less well-understood. In this work, we make progress on this question by considering the precise regime, in which one estimates the ground-state energy to within inverse exponential precision. Computing ground-state energies precisely is a task that is important for quantum chemistry and quantum many-body physics. In the setting of inverse-exponential precision, there is a surprising result that the complexity of LocalHamiltonian is magnified from QMA to PSPACE, the class of problems solvable in polynomial space. We clarify the reason behind this boost in complexity. Specifically, we show that the full complexity of the high precision case only comes about when the spectral gap is exponentially small. As a consequence of the proof techniques developed to show our results, we uncover important implications for the representability and circuit complexity of ground states of local Hamiltonians, the theory of uniqueness of quantum witnesses, and techniques for the amplification of quantum witnesses in the presence of postselection.

15:30 - 16:00 | Sample-efficient learning of quantum many-body systems

Authors: Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara and Mehdi Soleimanifar

Abstract

Affiliations: University of California, Berkeley | IBM T. J. Watson Research Center | RIKEN Center for Advanced Intelligence Project | MIT

Abstract
We study the problem of learning the Hamiltonian of a quantum many-body system given samples from its Gibbs (thermal) state. The classical analog of this problem, known as learning graphical models or Boltzmann machines, is a well-studied question in machine learning and statistics. In this work, we give the first sample-efficient algorithm for the quantum Hamiltonian learning problem. In particular, we prove that polynomially many samples in the number of particles (qudits) are necessary and sufficient for learning the parameters of a spatially local Hamiltonian in l2-norm. Our main contribution is in establishing the strong convexity of the log-partition function of quantum many-body systems, which along with the maximum entropy estimation yields our sample-efficient algorithm. Classically, the strong convexity for partition functions follows from the Markov property of Gibbs distributions. This is, however, known to be violated in its exact form in the quantum case. We introduce several new ideas to obtain an unconditional result that avoids relying on the Markov property of quantum systems, at the cost of a slightly weaker bound. In particular, we prove a lower bound on the variance of quasi-local operators with respect to the Gibbs state, which might be of independent interest. Our work paves the way toward a more rigorous application of machine learning techniques to quantum many-body problems.

16:00 - 16:30 | Asymptotic theory of quantum channel estimation

Authors: Sisi Zhou and Liang Jiang

Abstract

Affiliations: Yale University | University of Chicago

Extended abstract

Abstract
The quantum Fisher information (QFI), as a function of quantum states, measures the amount of information that a quantum state carries about an unknown parameter. The (entanglement-assisted) QFI of a quantum channel is defined to be the maximum QFI of the output state assuming an entangled input state over a single probe and an ancilla. In quantum metrology, people are interested in calculating the QFI of N identical copies of a quantum channel when N\rightarrow\infty, which we call the asymptotic QFI. It was known that the asymptotic QFI grows either linearly or quadratically with N. Here we obtain a simple criterion that determines whether the scaling is linear or quadratic. In both cases, the asymptotic QFI and a quantum error correction protocol to achieve it are solvable via a semidefinite program. When the scaling is quadratic, the Heisenberg limit, a feature of noiseless quantum channels, is recovered. When the scaling is linear, we show the asymptotic QFI is still in general larger than N times the single-channel QFI and furthermore, sequential estimation strategies provide no advantage over parallel ones. For details, see arXiv: 2003.10559.

16:30 - 17:00 | Round tables with Abhinav Deshpande, Mehdi Soleimanifar, and Sisi Zhou
At the end of the session, you can meet with the speakers directly. Round tables take place in parallel, each speaker having their own meeting.

##### 18:15 - 19:00 | Mingling

One on one networking session - a great way to meet new people, old friends, and make valuable connections. Participants get randomly matched for one on one talks for 3 minutes. You can try it at the 2D conference space (MeetAnyway).

### Session 3

Main stage (A)

##### 19:00 - 19:30 | Degree vs. Approximate Degree and Quantum Implications of Huangs Sensitivity Theorem

Authors: Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao and Avishay Tal

Abstract

Affiliations: The University of Texas at Austin | University of Waterloo | Microsoft | Northwestern University | University of California at Berkeley

Extended abstract

Abstract
Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function f, deg(f) = O(~deg(f)^2): The degree of f is at most quadratic in the approximate degree of f. This is optimal as witnessed by the OR function. D(f) = O(Q(f)^4): The deterministic query complexity of f is at most quartic in the quantum query complexity of f. This matches the known separation (up to log factors) due to Ambainis, Balodis, Belovs, Lee, Santha, and Smotrovs (2017). We apply these results to resolve the quantum analogue of the Aanderaa--Karp--Rosenberg conjecture. We show that if f is a nontrivial monotone graph property of an n-vertex graph specified by its adjacency matrix, then Q(f)=Omega(n), which is also optimal. We also show that the approximate degree of any read-once formula on n variables is Theta(sqrt{n}).

##### 19:30 - 20:30 | Fiber Bundle Codes: Breaking the N^{1/2} polylog(N) Barrier for Quantum LDPC Codes

Authors: Matthew Hastings, Jeongwan Haah and Ryan O'Donnell

Abstract

Affiliations: Microsoft | Microsoft | Carnegie Mellon University

Abstract
We present a quantum LDPC code family that has distance Omega(N^{3/5}/polylog(N)) and Theta(N^{3/5}) logical qubits, up to polylogs, where N is the code length. This is the first quantum LDPC code construction which achieves distance greater than N^{1/2} polylog(N). The construction is based on generalizing the homological product of codes to a fiber bundle.

##### 20:30 - 21:00 | Round tables with Shravas Rao, Matthew Hastings, and Jeongwan Haah

At the end of the session, you can meet with the speakers directly. Round tables take place in parallel, each speaker having their own meeting.

##### 21:00 - 22:30 | Munich Quantum Stammtisch

Ignacio Cirac invited experts on quantum computing to discuss with him in a casual atmosphere about „ Quo vadis quantum computers? ". Guests are Scott Aaronson (Texas Univ), Dorit Aharonov (Hebrew Univ.), Rainer Blatt (Univ. Innsbruck and AQT), John Martinis (UCSB and Sydney) and Mikhail Lukin (Harvard). Watch it live on YouTube .

##### 23:00 - 00:00 | Mentoring Session #2

Prior registration is required and only available for QIP 2021 participants. Specific times and dates are sent out via email.

##### 00:00 - 00:30 | Mingling

One on one networking session - a great way to meet new people, old friends, and make valuable connections. Participants get randomly matched for one on one talks for 3 minutes. You can try it at the 2D conference space (MeetAnyway).

Accept privacy?