Michael Vasmer: Fault-tolerant quantum computation with topological subsystem codes Quantum error correction seems to be indispensable in the quest to build a useful, i.e., fault-tolerant, quantum computer. Traditional approaches to quantum error correction rely on stabilizer codes such as the surface code. However, there exists a more general family of quantum error-correcting codes known as subsystem codes. Subsystem codes have advantages such as evading restrictions on transversal gates via a technique known as "gauge-switching" and increasing the logical clock speed via a phenomenon known as "single-shot error correction". In this talk I will discuss subsystem codes and their advantages, as exemplified by the recently introduced 3D subsystem toric code.

Zhengcheng Gu

Eric Chitambar: On the Duality of Teleportation and Dense Coding In this talk we'll revisit the classic problem of using noisy entanglement for teleportation. The first task will be to show how this problem can be rephrased as a state discrimination problem. In this picture, a quantitative duality between teleportation and dense coding emerges in which every Alice-to-Bob teleportation protocol can be repurposed as a Bob-to-Alice dense coding protocol, and the quality of each protocol can be measured by the success probability in the same state discrimination problem. One of our main results provides a complete characterization of the states that offer no advantage in one-way teleportation protocols over classical states, thereby offering a new and intriguing perspective on the long-standing open problem of identifying such states. Moreover, our established duality between teleportation and dense coding can be used to show that the exact same states are unable to provide a non-classical advantage for dense coding as well. As open an ongoing work, I will discuss the different bilinear optimization problems when studying the problem of noisy teleportation. This is joint work with Felix Leditzky (arXiv:2302.14798).

Discussion and Lunch Break

Yongsheng Zhang TBA

Masahito Hayashi: Two-Server Oblivious Transfer for Quantum Messages Oblivious transfer is considered as a cryptographic primitive task for quantum information processing over a quantum network. It is an essential building block for secure multiparty computation. It is known that one-server oblivious transfer is impossible. When the task is the transmission of classical messages, protocols for two-server oblivious transfer exist, i.e., existing protocols work under the assumption that two servers do not communicate with each other. However, when the task is the transmission of a quantum state, no existing method works even under the above two-server assumption. We propose two-server oblivious transfer protocols for quantum messages for the first time. The full paper is available from https://arxiv.org/abs/2211.03308

Nana Liu: Efficient quantum simulation of partial differential equations What kinds of scientific computing problems are suited to be solved on a quantum device with quantum advantage? It turns out that by transforming a partial differential equation (PDE) into a higher-dimensional space, it can be transformed into a system of Schrodinger’s equations, which is the natural dynamics of quantum devices. This new method – called Schrodingerisation – thus allows one to simulate, in a simple way, any general linear partial differential equation and system of linear ordinary differential equations via quantum simulation. Schrodingerisation can also be applied to problems in linear algebra by transforming iterative methods in linear algebra into evolution of ordinary differential equations, like the Jacobi method and the power method. This allows us to directly use quantum simulation to solve the linear system of equations and find maximum eigenvectors and eigenvalues of a given matrix. This method can be adapted to also solve boundary value problems like quantum dynamics with artificial boundary conditions, and also physical boundary conditions and interface conditions. I’ll also explore ways in which quantum algorithms can be used to efficiently simulate not just linear PDEs but also certain classes of nonlinear PDEs, like nonlinear Hamilton-Jacobi equations and scalar hyperbolic equations, which are useful in many areas like optimal control and machine learning. PDEs with uncertainties can also be tackled more efficiently with quantum algorithms.

Junyu Liu: Towards provably efficient quantum algorithms for large-scale machine-learning models TBA

Rahul Trivedi: Simulating many-body physics with noisy quantum devices Quantum computers offer a promising solution to the task of simulating many-body physics. A scalable fault-tolerant quantum computer with a large supply of logical qubits would allow us to answer many interesting questions about physical systems. In the near term we can only access noisy physical qubits, and this has raised an important theoretical question of identifying the limitations and applicability of near-term quantum hardware. I will first consider the circuit model of quantum computations, with the goal of the quantum circuit being to find the ground state of a specific Hamiltonian. Assuming that the circuits are interrupted by depolarizing errors, I will provide methods to lower bound the energy that can be achieved by the circuit and discuss the implications of these lower bounds on the ability of NISQ devices to find Hamiltonian ground states. In the next part of my talk, I will consider less pessimistic noise models (e.g. coherent errors) and I will show that for certain many-body physics problems, unencoded quantum computations or analogue quantum simulators could be practical. I will provide theoretical evidence that some many-body problems (related to both dynamics and equilibrium properties), are stable to errors and are likely solvable without error correction thus making them prime candidates for near-term experiments.

Discussion and Lunch Break

Xiaopeng Li: Quantum Reservoir Computing Searching for applications of programmable quantum simulation devices with quantum speedup has been attracting much research interests in recent years. In this talk, I would like to present quantum reservoir computing as a promising route to harness the computation power of quantum many-body dynamics. We find a quantum system at the edge of ergodic to non-ergodic phase transition has the best learning capacity on chaotic time sequence predictions. By configuring the quantum reservoir, we show this model is capable to perform multi-task learning, including gene regulatory networks, fractional Chua's circuit, and FX market forecast. Our configured quantum reservoir computing yields highly precise predictions for these learning tasks, outperforming classical reservoir computing. Through comparison with classical reservoir computing, we highlight the unique role of quantum coherence in the quantum reservoir, which underpins its exceptional learning performance. Our findings suggest the exciting potential of configured quantum reservoir computing for exploiting the quantum computation power of NISQ devices in developing general artificial intelligence.

Xiaoting Wang

Discussion

Giulio Chiribella: Thermodynamical nonequilibrium as a resource for accurate information processing Accurate information processing is crucial both in technology and in nature. To achieve it, any information processing system needs an initial supply of resources away from thermal equilibrium. In this talk, I will discuss the in-principle limits on the accuracy achievable with a given amount of nonequilibrium resources. Specifically, I will present a limit based on an entropic quantity, named the reverse entropy, associated to a time reversal of the information processing task under consideration. The limit is achievable for all deterministic classical computations and for all their quantum extensions. As an application, I will show the optimal tradeoffs between nonequilibrium and accuracy for the tasks of storing, transmitting, cloning, and erasing information. These results set a target for the design of new devices approaching the ultimate efficiency limit, and provide a framework for demonstrating thermodynamical advantages of genuine quantum information processing.

Nengkun Yu: Quantum Max-Flow Min-Cut theorem The max-flow min-cut theorem is a cornerstone result in combinatorial optimization. Calegari et al. (arXiv:0802.3208) initialized the study of quantum max-flow min-cut conjecture, which connects the rank of a tensor network and the min-cut. Cui et al. (arXiv:1508.04644) showed that this conjecture is generally false. This paper establishes a quantum max-flow min-cut theorem for a new definition of quantum maximum flow. In particular, we show that for any quantum tensor network, there are infinitely many n, such that quantum max-flow equals quantum min-cut, after attaching a dimension maximally entangled state to each edge as ancilla. Our result implies that the ratio of the quantum max-flow to the quantum min-cut converges to 1 as the dimension n tends to infinity. As a direct application, we prove the validity of the asymptotical version of the open problem about the quantum max-flow and the min-cut, proposed in Cui et al. (arXiv:1508.04644 ). The link to this paper is arXiv:2110.00905.

Tomoyuki Morimae: Quantum commitments and signatures without one-way functions In the classical world, the existence of commitments is equivalent to the existence of one-way functions. In the quantum setting, on the other hand, commitments are not known to imply one-way functions, but all known constructions of quantum commitments use at least one-way functions. Are one-way functions really necessary for commitments in the quantum world? In this work, we show that non-interactive quantum commitments (for classical messages) with computational hiding and statistical binding exist if pseudorandom quantum states exist. Pseudorandom quantum states are sets of quantum states that are efficiently generated but their polynomially many copies are computationally indistinguishable from the same number of copies of Haar random states [Ji, Liu, and Song, CRYPTO 2018]. It is known that pseudorandom quantum states exist even if BQP=QMA (relative to a quantum oracle) [Kretschmer, TQC 2021], which means that pseudorandom quantum states can exist even if no quantum-secure classical cryptographic primitive exists. Our result therefore shows that quantum commitments can exist even if no quantum-secure classical cryptographic primitive exists. In particular, quantum commitments can exist even if no quantum-secure one-way function exists. In this work, we also consider digital signatures, which are other fundamental primitives in cryptography. We show that one-time secure digital signatures with quantum public keys exist if pseudorandom quantum states exist. In the classical setting, the existence of digital signatures is equivalent to the existence of one-way functions. Our result, on the other hand, shows that quantum signatures can exist even if no quantum-secure classical cryptographic primitive (including quantum-secure one-way functions) exists.

Discussion and Lunch Break

Dong Liu: Lattice gauge theory and topological quantum error correction with quantum deviations in the state preparation and error detection Quantum deviations or coherent noise are a typical type of noise when implementing gate operations in quantum computers, and their impact on the performance of quantum error correction (QEC) is still elusive. Here, we consider the topological surface code, with both stochastic noise and coherent noise on the multi-qubit entanglement gates during stabilizer measurements in both initial state preparation and error detection. We map a multi-round error detection protocol to a three-dimensional statistical mechanical model consisting of Z_2 gauge interactions and related the error threshold to its phase transition point. Specifically, two error thresholds are identified distinguishing different error correction performances. Below a finite error threshold, in stark contrast to the case with only stochastic errors, unidentifiable measurement errors can cause the failure of QEC in the large code distance limit. This problem can only be fixed at the perfect initial state preparation point. For a finite or small code with distance d, we find that if the preparation error rate is below a crossover scale ~1/\log(d), the logical errors can still be suppressed. We conclude that this type of unavoidable coherent noise has a significant impact on QEC performance, and becomes increasingly detrimental as the code distance increases.

Tongyang Li: Quantum Algorithms for Nonconvex Optimization The theories of optimization answer foundational questions in statistics, operations research, machine learning, etc., and lead to new algorithms for practical applications. In this talk, I will introduce quantum algorithms for nonconvex optimization, which are very much motivated by intuitions from quantum physics. In particular, given a function f: R^n → R, our quantum algorithm outputs an ε-approximate second-order stationary point using O(log n / ε^1.75) queries to the quantum evaluation oracle (i.e., the zeroth-order oracle). Compared to the classical algorithm by Jin et al. using O((log n)^6 / ε^1.75) queries to the gradient oracle (i.e., the first-order oracle), our quantum algorithm is polynomially better in terms of log n and matches its complexity in terms of 1/ε. Technically, our main contribution is the idea of replacing the classical perturbations in gradient descent methods by simulating the evolution of the Schrodinger equation. In the end, we will also briefly introduce our recent development in quantum algorithms for general nonconvex optimization problems.

Discussion