召集人：王鑫（香港科技大学（广州），副教授）、尚云（中国科学院数学与系统科学研究院，研究员）、高斌（中国科学院数学与系统科学研究院，副研究员）

时间：2025.04.13—2025.04.19

Organization of the Program

Workshop Schedule 

Titles and Abstracts 

09:00-10:00, Apr. 14, Monday Speaker: Jingsong Huang

 Title: Invariant Theory in Quantum Computing

Abstract: Algebraic and geometric invariants have been extensively studied in algebra and geometry.  Both classical invariant theory and geometric invariant theory play important roles in the current development of representation theory and algebraic geometry. In this talk, we discuss application of the invariant theory to implementation of the quantum Fourier transform and measurement of the quantum entanglement.

10:30-11:00, Apr. 14, Monday Speaker: Dong An

Title: Quantum algorithms for linear differential equations

Abstract: Designing quantum algorithms for solving linear differential equations has attracted great attention due to its potential exponential speedup over classical algorithms and its fundamental role in scientific and engineering computation. In this talk, we will discuss how to design a generic quantum linear differential equation algorithm with near-optimal complexity in all parameters. The idea of the algorithm is based on the linear combination of Hamiltonian simulation technique. In addition, for dissipative differential equations, we will discuss a fast-forwarded quantum algorithm with further improved time complexity.

11:00-11:30, Apr. 14, Monday Speaker: Jinguo Liu 

Title: Automated Discovery of Branching Rules with Optimal Complexity for the Maximum Independent Set Problem

Abstract: The branching algorithm is a fundamental technique for designing fast exponential-time algorithms to solve combinatorial optimization problems exactly. It divides the entire solution space into independent search branches using predetermined branching rules, and ignores the search on suboptimal branches to reduce the time complexity. The complexity of a branching algorithm is primarily determined by the branching rules it employs, which are often designed by human experts. In this paper, we show how to automate this process with a focus on the maximum independent set problem. The main contribution is an algorithm that efficiently generates optimal branching rules for a given sub-graph with tens of vertices. Its efficiency enables us to generate the branching rules on-the-fly, which is provably optimal and significantly reduces the number of branches compared to existing methods that rely on expert-designed branching rules. Numerical experiments on 3-regular graphs shows an average complexity of O(1.0441^n) can be achieved, better than any previous methods.

11:30-12:00, Apr. 14, Monday Speaker: Yuxiang Yang

Title: Fully-optimized quantum metrology

Abstract: One of the main quests in quantum metrology is to attain the ultimate precision limit with given resources, where the resources are not only of the number of queries, but more importantly of the allowed strategies. With the same number of queries, the restrictions on the strategies constrain the achievable precision. In this talk, I will introduce a systematic framework to identify the ultimate precision limit of different families of strategies, including the parallel, the sequential and the indefinite-causal order strategies, and provide an efficient algorithm that determines an optimal strategy within the family of strategies under consideration. With this framework, we can show there exists a strict hierarchy of the precision limits for different families of strategies.

14:30-15:30, Apr. 14, Monday Speaker: Huangjun Zhu

Title: Nonstabilizerness Enhances Thrifty Shadow Estimation

Abstract: Shadow estimation is a powerful approach for estimating the expectation values of many observables. Thrifty shadow estimation is a simple variant that is proposed to reduce the experimental overhead by reusing random circuits repeatedly. Although this idea is so simple, its performance is quite elusive. In this work we show that thrifty shadow estimation is effective on average whenever the unitary ensemble forms a 2-design, in sharp contrast with the previous expectation. In thrifty shadow estimation based on the Clifford group, the variance is inversely correlated with the degree of nonstabilizerness of the state and observable, which is a key resource in quantum information processing. For fidelity estimation, it decreases exponentially with the stabilizer 2-Rényi entropy of the target state, which endows the stabilizer 2-Rényi entropy with a clear operational meaning. In addition,we propose a simple circuit to enhance the efficiency, which requires only one layer of T gates and is particularly appealing in the NISQ era.

16:00-16:30, Apr. 14, Monday Speaker: Changpeng Shao

Title: Randomized quantum singular value transformation

Abstract: In this talk, I will introduce a recent work with Shantanav Chakraborty, Soumyabrata Hazra, Tongyang Li, Xinzhao Wang and Yuxin Zhang (arXiv:2504.02385). The talk is about implementing quantum singular value transformation without block-encoding, assuming the input matrix is given as a linear combination of unitaries. We propose algorithms achieving near optimal complexity, meanwhile only use 1 ancilla qubit.

16:30-17:00, Apr. 14, Monday Speaker: Yu-Ao Chen

Title: Optimal Quantum Hypothesis Testing of Unitary Distributions

Abstract: Symmetry is fundamental in quantum physics, governing the behavior and dynamics of physical systems. We develop a hypothesis-testing framework for quantum dynamics symmetry based on querying an unknown unitary operation. Leveraging the symmetry properties of compact groups and their irreducible representations, we characterize the optimal type-II error in unitary subgroup hypothesis testing and demonstrate that parallel, adaptive, indefinite causal order, and general strategies are equally powerful in achieving this optimal error rate. Furthermore, we present a general solution for evaluating the optimal type-II error, which depends solely on the irreducible representations of the group and its subgroup. Applying our results to hypothesis testing of U(2) over the singleton group, maximal commutative group, and orthogonal group, we provide analytical and optimal characterizations of type-II error for predicting identity, Z-symmetry, and T-symmetry in unknown qubit unitary operations. Additionally, we extend our analysis to the hypothesis testing of the groups  and  within U(2), showing that adaptive and general strategies achieve the same optimal type-II error, with the adaptive strategy fitting within the quantum signal processing framework.

 09:00-10:00, Apr. 15, Tuesday Speaker: Shi Jin

Title: Dimension Lifting for Quantum Computation of  partial differential equations and related problems

Abstract: Quantum computers have the potential to gain algebraic and even up to exponential speed up compared with its classical counterparts, and can lead to technology revolution in the 21st century. Since quantum computers are designed based on quantum mechanics principle, they are most suitable to solve the Schrodinger equation, and linear PDEs (and ODEs) evolved by unitary operators.  The most efficient quantum PDE solver is quantum simulation based on solving the Schrodinger equation. It will be interesting to explore what other problems in scientific computing, such as ODEs, PDEs, and  linear algebra that arise in both classical and quantum systems,  can be handled by quantum simulation.  

We will present a systematic way to develop quantum simulation algorithms for general differential equations. Our basic framework is dimension lifting, that transfers nonlinear PDEs to linear ones, and linear ones to Schrodinger type PDEs. For non-autonomous PDEs and ODEs, or Hamiltonian systems with time-dependent Hamiltonians,  we also add an extra dimension to transform them into autonomous PDEs that have only time-independent coefficients, thus quantum simulations can be done without using the cumbersome Dyson’s series and time-ordering operators. Our formulation allows both qubit and qumode (continuous-variable) formulations, and their hybridizations, and provides the foundation for analog quantum computing.

10:30-11:00, Apr. 15, Tuesday Speaker: Haidong Yuan

Title: Incompatibility measures in multi-parameter quantum estimation under hierarchical quantum measurements

Abstract: The incompatibility of the optimal measurements for the estimation of different parameters constraints the achievable precisions in multi-parameter quantum estimation. Understanding the tradeoff induced by such incompatibility is thus a central topic in quantum metrology. Here we provide an approach to study the incompatibility in terms of information geometry. We demonstrate the power of the approach by present a hierarchy of analytical tradeoff relations induced by the incompatibility.

11:00-11:30, Apr. 15, Tuesday Speaker: Ge Bai

Title: Quantum Bayes' rule and Petz transpose map from the minimum change principle.

Abstract: Bayes' rule, which is routinely used to update beliefs based on new evidence, can be derived from a principle of minimum change. This principle states that updated beliefs must be consistent with new data, while deviating minimally from the prior belief. Here, we introduce a quantum analog of the minimum change principle and use it to derive a quantum Bayes' rule by minimizing the change between two quantum input-output processes, not just their marginals. This is analogous to the classical case, where Bayes' rule is obtained by minimizing several distances between the joint input-output distributions. When the change maximizes the fidelity, the quantum minimum change principle has a unique solution, and the resulting quantum Bayes' rule recovers the Petz transpose map in many cases.

11:30-12:00, Apr. 15, Tuesday Speaker: Naixu Guo

Title: Design nearly optimal quantum algorithm for linear differential equations via Lindbladians

Abstract: Solving linear ordinary differential equations (ODE) is one of the most promising applications for quantum computers to demonstrate exponential advantages. The challenge of designing a quantum ODE algorithm is how to embed non-unitary dynamics into intrinsically unitary quantum circuits. In this work, we propose a new quantum algorithm for ODEs by harnessing open quantum systems. Specifically, we utilize the natural non-unitary dynamics of Lindbladians with the aid of a new technique called the non-diagonal density matrix encoding to encode general linear ODEs into non-diagonal blocks of density matrices. This framework enables us to design a quantum algorithm that has both theoretical simplicity and good performance. Combined with the state-of-the-art quantum Lindbladian simulation algorithms, our algorithm, under a plausible input model, can outperform all existing quantum ODE algorithms and achieve near-optimal dependence on all parameters. We also give applications of our algorithm including the Gibbs state preparations and the partition function estimations.

14:30-15:30 Apr. 15, Tuesday Speaker: Yuling Jiao

Title: DRM Revisited: A Complete Error Analysis

Abstract: The error analysis of deep learning includes approximation error, statistical error, and optimization error. However, existing works often struggle to integrate these three types of errors due to overparameterization. In this talk, we aim to bridge this gap by addressing a key question in the analysis of the Deep Ritz Method (DRM): "Given a desired level of precision, how can we determine the number of training samples, the parameters of neural networks, the step size of gradient descent, and the number of iterations needed so that the output deep networks from gradient descent closely approximate the true solution of the PDEs with the specified precision?"

09:00-9:30, Apr. 16, Wednesday Speaker: Yingzhou Li

Title: Quantum Circuit for Non-Unitary Linear Transformation of Basis Sets

Abstract: This talk introduces a novel approach to implementing non-unitary linear transformations of basis on quantum computational platforms, a significant leap beyond the conventional unitary methods. By integrating Singular Value Decomposition (SVD) into the process, the method achieves an operational depth of O(n) with at most n ancilla qubits, enhancing the computational capabilities for analysing fermionic systems. By this trick, we can calculate two ansatzes’ overlap which live in two different basis. This allows us to orthogonalize the ansatzes under different basis sets, which provides the opportunity to use ansatzes from different basis sets to calculate different energy eigenstates and improve the accuracy when computing the energies of multiple eigenstates simultaneously. This novel approach allows for a deeper exploration of complex quantum states and phenomena, expanding the practical applications of quantum computing in physics and chemistry.

9:30-10:00, Apr. 16, Wednesday Speaker: Jie Wang

Title: State Polynomial Optimization and Nonlinear Bell Inequalities

Abstract: State polynomials are polynomials in noncommuting variables and formal states of their products. We present a complete hierarchy of semidefinite relaxations for solving state polynomial optimization problems. This hierarchy can be seen as a state analog of the Navascues-Pironio-Acin scheme for optimization of noncommutative polynomials. The motivation behind this theory arises from the study of correlations in quantum networks. Determining the maximal quantum violation of a polynomial Bell inequality for an arbitrary network is reformulated as a state polynomial optimization problem.

10:30-11:00, Apr. 16, Wednesday Speaker: Tianyu Wang

Title: Convex Optimization over Alexandrov Spaces: A Quasi-linearization Approach

Abstract: We study convergence results for classis optimization problems over Hadamard manifolds, with the boundedness assumptions completely removed. Our result is achieved via quasi-linearization of the Alexandrov spaces.

11:00-11:30, Apr. 16, Wednesday Speaker: Ruchi Guo

Title: Optimization and preconditioning: TPDv algorithms for nonlinear PDEs

Abstract: In physics and mathematics, a large class of PDE systems can be formulated as minimizing energy functionals subject to certain constraints. Lagrange multipliers are widely used for solving these problems, which however leads to minmax optimization problems, i.e., saddle point systems. The development of fast solvers for saddle point systems, especially the nonlinear ones, is particularly difficult in the sense that (i) one has to consider the preconditioning in two directions and (ii) the preconditioners have to evolve in iteration due to the nonlinearity. In this work, we introduce an efficient transformed primal-dual (TPD) algorithm to solve the aforementioned nonlinear saddle point problems. In this work, we introduce an efficient transformed primal-dual (TPD) algorithm to solve the aforementioned nonlinear saddle point problems.

11:30-12:00, Apr. 16, Wednesday Speaker: Yinan Li

Title: Rigorous QROM Security Proofs for Some Post-Quantum Signature Schemes Based on Group Actions

Abstract: Group action based cryptography was formally proposed in the seminal paper of Brassard and Yung (Crypto ’90) and recently further developed by Ji et al. (TCC ’19) and Alamati et al. (AsiaCrypt ’19). Three submissions to the NIST’s call for additional post-quantum digital signatures, such as ALTEQ and MEDS, are based on one-way group actions. One approach to proving the QROM security for these group action based schemes uses the perfect unique response property introduced by Unruh (Eurocrypt ’12; AsiaCrypt ’17). In the contexts of ALTEQ and MEDS, this means that a random element does not have a non-trivial automorphism. Before this work, only computational evidence for small dimensions (Bläser et al., PQCrypto ’24; Reijnders–SamardjiskaTrimoska, Des. Codes Cryptogr. ’24) or subexponential bounds (Li–Qiao, FOCS ’17) are known. In this work, we formally prove that the average order of stabilizer groups is asymptotically trivial. As a result, when the dimension is large enough, all but an exponentially small fraction of alternating trilinear forms or matrix codes have the trivial stabilizer, confirming the assumptions for alternating trilinear forms (ALTEQ) and matrix codes (MEDS). Our approach is to examine the fixed points of the induced action of an invertible matrix over a finite field on trilinear forms.

09:00-9:30, Apr. 17, Thursday Speaker: Li Gao

Title: Convex Splitting: tight analysis and multipartite case

Abstract: Convex splitting is a powerful tool in quantum information that has been used in many information-processing protocols such as quantum state redistribution and quantum channel coding. In this talk, we will present some near optimal one-shot estimates for convex splitting which yields matched second-order asymptotics as well as error and strong converse exponent. Moreover, using an interesting decomposition, our error exponent estimate also applies to multipartite case, which leads to the resolution of Quantum Broadcast Channel Simulation. This talk is based on joint works with Hao-Chung Cheng and Mario Berta.

 09:30-10:00, Apr. 17, Thursday Speaker: Bujiao Wu

Title: Linear properties of quantum states

Abstract: Estimating properties of quantum states, such as fidelities, molecular energies, and correlation functions, is a central challenge in quantum information science. A key question is how to perform these estimations efficiently. This talk addresses this question by exploring research on randomized measurement techniques and related protocols for optimizing the expectation values of observables. Topics covered include: (1) classical shadows in qubit and fermionic systems, both with and without error mitigation, (2) randomized measurement schemes based on Pauli decomposition, and (3) algorithms leveraging quantum parameterized circuits for randomized measurements.

 10:30-11:00, Apr. 17, Thursday Speaker: Kun Fang

Title: Generalized quantum asymptotic equipartition

Abstract: We establish a generalized quantum asymptotic equipartition property (AEP) beyond the i.i.d. framework where the random samples are drawn from two sets of quantum states. In particular, under suitable assumptions on the sets, we prove that all operationally relevant divergences converge to the quantum relative entropy between the sets. More specifically, both the smoothed min- and max-relative entropy approach the regularized relative entropy between the sets. Notably, the asymptotic limit has explicit convergence guarantees and can be efficiently estimated through convex optimization programs, despite the regularization, provided that the sets have efficient descriptions. We give four applications of this result: (i) The generalized AEP directly implies a new generalized quantum Stein's lemma for conducting quantum hypothesis testing between two sets of quantum states. (ii) We introduce a quantum version of adversarial hypothesis testing where the tester plays against an adversary who possesses internal quantum memory and controls the quantum device and show that the optimal error exponent is precisely characterized by a new notion of quantum channel divergence, named the minimum output channel divergence. (iii) We derive a relative entropy accumulation theorem stating that the smoothed min-relative entropy between two sequential processes of quantum channels can be lower bounded by the sum of the regularized minimum output channel divergences. (iv) We apply our generalized AEP to quantum resource theories and provide improved and efficient bounds for entanglement distillation, magic state distillation, and the entanglement cost of quantum states and channels. At a technical level, we establish new additivity and chain rule properties for the measured relative entropy which we expect will have more applications.

11:00-11:30, Apr. 17, Thursday Speaker: Zhijian Lai

Title: Optimal Interpolation-based Coordinate Descent Method for Variational Quantum Algorithms

Abstract: In this paper, we propose an optimal interpolation-based coordinate descent (OICD) method to solve the classical optimization problem that arises in variational quantum algorithms (VQAs).  The OICD method reduces the cost burden on quantum devices by approximating the cost functions through interpolation method. Specifically, by using a trigonometric polynomial model to represent univariate constraint functions (i.e., involving only one tunable parameter), OICD efficiently captures the key information needed for optimization. A key aspect of the OICD method is the selection of appropriate interpolation points to minimize noise impact. To this end, we numerically determine the optimal interpolation points during the OICD’s preparation phase. Remarkably, for the case of equidistant frequencies (where the Hermitian generator in quantum circuit is typically a Pauli word), we have theoretically proven that the optimal interpolation points are  -equidistant points, and this scheme satisfies three different criteria simultaneously

11:30-12:00, Apr. 17, Thursday Speaker: Zhan Yu

Title: Quantum signal processing in machine learning and algorithm design

Abstract：Quantum Signal Processing (QSP) has emerged as a unifying framework that enables the precise manipulation of quantum amplitudes through the composition of simple unitary operations. This talk explores how QSP serves as a powerful algorithmic primitive in both quantum machine learning and quantum algorithm design. We first delve into the expressive power of QSP-based parameterized quantum circuits (PQCs), which can approximate a broad class of continuous functions—paving the way for PQCs that rival or surpass their classical counterparts in machine learning. We then develop the multi-qubit generalization of QSP, which provides a powerful framework for efficient quantum algorithm design. Throughout the talk, we emphasize the interplay between rigorous algorithmic guarantees and practical circuit implementations, illustrating how QSP bridges theoretical insights in quantum algorithms and quantum machine learning.

14:30-15:00, Apr. 17, Thursday Speaker: Yin Mo

Title: Parameterized Quantum Comb and Reversing Unknown Unitary Evolutions

Abstract: Reversing an unknown unitary evolution remains a formidable challenge, as conventional methods necessitate an infinite number of queries to fully characterize the quantum process. Here we introduce the Quantum Unitary Reversal Algorithm (QURA), a deterministic and exact approach to universally reverse arbitrary unknown unitary transformations using O(d^2) calls of the unitary, where d is the system dimension. Our construction resolves a fundamental problem of time-reversal simulations for closed quantum systems by affirming the feasibility of reversing any unitary evolution without knowing the exact process. Besides introducing the algorithm, I will also talk about the framework we used for developing this algorithm, which combines the idea of parameterized quantum circuit and quantum comb, and further discuss its potential for solving complex quantum tasks.

15:00-15:30, Apr. 17, Thursday Speaker: Minbo Gao

Title: 量子近似k最小值查找

Abstract: 量子k最小值查找是一个基础且重要的量子算法，在组合问题和机器学习中有许多应用。以往方法往往假设有精确的函数值查询喻示作为算法输入，这使得其不容易与其他量子算法相组合。我们在van Apeldoorn, Gilyén, Gribling和de Wolf等人工作的基础上，提出了一个新的只使用近似值查询喻示的量子k最小值查找算法，该算法具有近似最优的复杂度。作为该算法的实际应用，我们提出了用于识别多个可观测量中的k个最小期望值，以及确定具有已知本征基的哈密顿量的k个最低基态能量的高效的量子算法。

9:00-10:00, Apr. 18, Friday Speaker: Penghui Yao 

Title: Some Applications of Pauli analysis on Quantum Algorithms and Complexity

Abstract: Fourier analysis is playing a pivotal role in designing quantum algorithms. Recently, Fourier analysis on the space of operators and the space of super-operators, which is termed as Pauli analysis, has received increasing attention. It has found connections to various areas of quantum computing. In this talk, I will introduce some background on Pauli analysis and present some recently discovered applications in quantum learning theory and quantum complexity theory.

10:30-11:00, Apr. 18, Friday Speaker: Yadong Wu

Title: 神经网络学习量子系统

Abstract: 人工智能技术已广泛应用于解决各类物理问题，包括量子信息与量子计算领域。与此同时，高效测量并学习未知量子系统及预测其特性，已成为近期量子信息与量子机器学习研究的热点。在本报告中，我将展示一系列利用神经网络算法表征未知量子系统的研究成果。在这些研究中，我们通过神经网络算法从随机采样的测量数据中提取量子系统的经典表示，并基于该表示准确预测量子系统的物理特性。这一系列工作为多体量子系统和光学量子系统的刻画与表征提供了一个数据驱动的方法框架。

11:00-11:30, Apr. 18, Friday Speaker: Lingling Lao

Title: Decoding algorithms for surface codes

Abstract: The primary obstacle to achieving large-scale reliable quantum computing is noise. Quantum error correction (QEC) addresses this by encoding multiple noisy physical qubits into a logical qubit. One can exponentially suppress the logical error rate by increasing the code distance when the physical error rate falls below a specific threshold. The performance of decoding directly affects the logical error rates, and the decoding speed must exceed the cycle time of a QEC round. This talk will discuss different decoding algorithms for surface codes. 

11:30-12:00, Apr. 18, Friday Speaker: Xuanqiang Zhao

Title: Advantages of indefinite causal order in communication

Abstract: We develop a resource theory of communication that incorporates indefinite causal order. We show that, given the same amount of resource, there are instances where causally indefinite operations offer explicit advantages over causally definite ones. However, for Pauli channels, we find that causally definite operations perform equally well as causally indefinite ones, indicating no advantage from indefinite causal order in this case. Our framework allows for a direct comparison of operations with different causal structures on an equal footing and can be extended to other resource theories beyond communication, providing a foundational step towards understanding the advantages of indefinite causal order in various quantum information processing tasks.