Research area 01
Quantum algorithms & optimization
Hamiltonian-oriented algorithms for optimization and scientific computing, from theoretical foundations to implementation.
Explore this areaResearch
Toward End-to-End Quantum Applications
This is an exciting yet challenging era for quantum computing. While early-stage quantum computers are now accessible via the cloud, the resources needed to fully realize their potential far exceed current capabilities. Bridging the gap between theory and practice is crucial to translating quantum computing’s theoretical promise into real-world applications. This requires not only advancing quantum hardware but also developing theory for practical quantum applications, efficient and reliable operating/control systems, and intuitive yet effective programming interfaces to enable a full-stack application-oriented co-design to maximize the utility of quantum hardware for practical applications.
Research Goals
My research aims to fill these gaps by providing the foundations for end-to-end quantum applications. To this end, I actively explore the intersection of quantum computing with diverse disciplines, including theoretical computer science, machine learning, control theory, formal methods, programming languages, and computer architecture. This multidisciplinary approach brings fresh (and necessary) perspectives and expertise to advance practical and scalable quantum computing. A defining feature of my research is holistic software-hardware-algorithmic co-design.
Research area 02
Quantum machine learning
Quantum learning algorithms, variational methods, and differentiable quantum programming.
Explore this areaResearch area 03
Quantum programming & verification
Formal verification, program synthesis, and foundations for dependable quantum applications.
Explore this areaResearch area 04
Quantum systems & architecture
Programming interfaces, real-time control, and hardware–software co-design for quantum devices.
Explore this areaHamiltonian-oriented Quantum Algorithm Design and Programming
The conventional design of quantum algorithms is centered around the abstraction of quantum circuits and relies on a digital mindset for application design and implementation. While serving as an elegant mathematical interface, circuit-based digital abstraction usually fails to capture the native programmability of quantum devices and incurs large overheads. These overheads significantly restrict its near-term feasibility, where computing resources are the major limitation. Historically, circuit-based digital abstraction has successfully scaled up the design and implementation of modern classical computing chips in a setting with abundant computing resources, where correctness becomes a major issue for scalability. The benefits of circuit-based digital abstraction for quantum computing are more limited when scarce computing resources are the major near-term bottleneck.
We therefore propose to use quantum Hamiltonian evolution as the central object in end-to-end quantum application design, the so-called Hamiltonian-oriented paradigm, based on the observation that Hamiltonian evolution is a native abstraction for both low-level hardware control and high-level quantum applications. We illustrate that the Hamiltonian-oriented design not only allows more efficient implementation of known quantum algorithms but also inspires novel quantum algorithms, especially in optimization and scientific computing, which are hard to identify in the circuit model. We also develop a programming infrastructure for easy implementation of Hamiltonian-based quantum applications for domain experts on heterogeneous quantum devices.
Quantum Hamiltonian Descent
Gradient-based methods are important optimization techniques that are prevalent in both theoretical and empirical studies. A quantum counterpart of gradient-based methods, however, has been missing. Inspired by the correspondence between gradient-based methods and physics-inspired dynamical systems, we propose a quantization of such correspondence based on the path integral formulation of quantum mechanics, which in turn implies a quantum extension of gradient descent called quantum Hamiltonian descent (QHD). We proved QHD’s global convergence under suitable assumptions for non-convex functions with a unique global minimum and observed faster convergence than the classical algorithms tested and the quantum adiabatic algorithm on a benchmark set of hard instances in non-convex optimization. Excitingly, QHD could be realized on either circuit-based or analog (e.g., quantum simulators) quantum machines for a scalable empirical study. Our finding also opens the possibility of a unified framework for both quantum and classical gradient-based methods.
Publications:
Quantum Hamiltonian Descent. Jiaqi Leng, Ethan Hickman, Joseph Li, and Xiaodi Wu. Preprint, 2023. arXiv Project
A Quantum-Classical Performance Separation in Nonconvex Optimization. Jiaqi Leng, Yufan Zheng, and Xiaodi Wu. Preprint, 2023. arXiv Code
A quantum central path algorithm for linear optimization. Brandon Augustino, Jiaqi Leng, Giacomo Nannicini, Tamas Terlaky and Xiaodi Wu. Preprint, 2023. Workshop presentation: QIP 2025 (contributed talk). arXiv
QHDOPT: A Software for Nonlinear Optimization with Quantum Hamiltonian Descent. Samuel Kushnir, Jiaqi Leng, Yuxiang Peng, Lei Fan, and Xiaodi Wu. INFORMS Journal on Computing 37(1), 107–124 (2025). Code DOI arXiv
Quantum Hamiltonian Descent for Non-smooth Optimization. Jiaqi Leng, Yufan Zheng, Zhiyuan Jia, Lei Fan, Chaoyue Zhao, Yuxiang Peng, and Xiaodi Wu. Preprint, 2025. arXiv
(Sub)Exponential Quantum Speedup for Optimization. Jiaqi Leng, Kewen Wu, Xiaodi Wu, Yufan Zheng. Preprint, 2025. arXiv
Hamiltonian Embedding
The realization of quantum computing is fundamentally based on the precise manipulation of Hilbert spaces of underlying quantum devices. The conventional wisdom relies on circuit synthesis techniques to decompose sophisticated operations on Hilbert space into a set of universal elementary gates. Although providing a universal solution in principle, this hardware-agnostic strategy typically leads to deep quantum circuits for interesting quantum algorithms, which makes them infeasible for implementation on near-term quantum devices. We propose a technique named Hamiltonian embedding that simulates a desired Hamiltonian evolution by embedding it into the evolution of a large and structured quantum system, which, however, allows more efficient manipulation via hardware-native operations. We conduct a systematic study of this embedding technique and demonstrate significant computational resource savings for implementing prominent quantum applications. As a result, we can experimentally realize quantum walks on complicated graphs (e.g., binary trees, glued-tree graphs), quantum spatial search, and the simulation of real-space Schrödinger equations on trapped-ion and neutral-atom platforms today. Given the fundamental role of Hamiltonian evolution in quantum algorithm design, our technique significantly expands the horizon of implementable quantum advantage in the NISQ era.
Publications:
Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding. Jiaqi Leng*, Joseph Li*, Yuxiang Peng, and Xiaodi Wu. Quantum 9, 1857 (2025). arXiv DOI
Differentiable Analog Quantum Computing
We formulate the first differentiable analog quantum computing framework with a specific parameterization design at the analog signal (pulse) level to better exploit near-term quantum devices via variational methods. We further propose a scalable approach to estimate the gradients of quantum dynamics using a forward pass with Monte Carlo sampling, which leads to a quantum stochastic gradient descent algorithm for scalable gradient-based training in our framework. Applying our framework to quantum optimization and control, we observe a significant advantage of differentiable analog quantum computing over state-of-the-art methods based on parameterized digital quantum circuits, by orders of magnitude.
Publications:
Differentiable Analog Quantum Computing for Optimization and Control. Jiaqi Leng*, Yuxiang Peng*, Yi-Ling Qiao*, Ming C. Lin, and Xiaodi Wu. Advances in Neural Information Processing Systems 35 (NeurIPS 2022). arXiv Code Proceedings
Full-Stack Software & System Co-design for Quantum Applications
End-to-end quantum application design benefits greatly from a full-stack, open-source, and reconfigurable quantum software system that interfaces seamlessly with domain users and quantum hardware. We demonstrate the feasibility of such a holistic approach and contribute to co-design automation, particularly by addressing challenges like quantum noise and limited system sizes using theoretical insights and machine learning techniques.
Domain-specific Abstraction & Programming.
A central challenge in programming language design is creating abstractions that help developers maximize the potential of target computing devices. To address this for resource-constrained near-term quantum computers, we propose a new quantum programming language, SimuQ (Simulation language for Quantum) (POPL’24). Inspired by pioneering languages like FORTRAN and SIMULA, SimuQ treats Hamiltonian evolution as a fundamental abstraction for quantum computation, a counterpart to floating-point arithmetic in classical computing, and supports compilation to both gate-based and pulse-programmable quantum backends. It has garnered significant commercial interest, including collaborations with AWS Braket, Mathematica, and MATLAB, and was a finalist for the University of Maryland’s Innovation of the Year award.
Publications:
SimuQ: A Framework for Programming Quantum Hamiltonian Simulation with Analog Compilation. Yuxiang Peng, Jacob Young, Pengyu Liu, and Xiaodi Wu. Proceedings of the ACM on Programming Languages 8 (POPL), 2425–2455 (2024). arXiv Project DOI
Quantum Real-Time Systems
Quantum computing requires precise timing, rapid feedback, and scalable control. In our work on quantum control systems, we introduce RISC-Q, an open-source generator for Quantum Control System-on-Chip (QCSoC) designs with a programming interface compatible with the RISC-V ecosystem. Adopting a software-oriented, agile hardware design approach, RISC-Q provides a highly parameterized, modular framework for creating custom controllers deployable on FPGA or ASIC platforms. This supports rapid prototyping and iterative exploration of the hardware–software co-design space as quantum control needs evolve.
RISC-Q allows on-chip calibration, control, sensing, and learning protocols with feedback to be developed in familiar languages such as C and Rust. Its architecture brings together signal processing, real-time control, custom accelerators, and communication across boards. RISC-Q-generated controllers can execute instructions compiled by SimuQ, together forming a minimal example of a full-stack software system for quantum simulation. This is further exemplified by QHDOPT, which is built on top of SimuQ. This integration enables co-design with minimal overhead, enhancing efficiency and adaptability in quantum application development.
Building on RISC-Q, we have also developed a scalable, open-source quantum error correction system that integrates qubit control, multi-board communication, and hardware decoding in a complete decoding-feedback pipeline. This work studies the performance of the whole real-time system, including the interaction between control, communication, and decoding.
Publications:
RISC-Q: A Generator for Real-Time Quantum Control System-on-Chips Compatible with RISC-V. Junyi Liu, Yi Lee, Haowei Deng, Connor Clayton, Gengzhi Yang, and Xiaodi Wu. DAC 2026. arXiv Code Project DAC
A Scalable Open-Source QEC System with Sub-Microsecond Decoding-Feedback Latency. Junyi Liu, Yi Lee, Yilun Xu, Gang Huang, and Xiaodi Wu. IEEE International Conference on Quantum Computing and Engineering (QCE 2026), IEEE Quantum Week. arXiv Code QCE program
Quantum Networks
We are developing a programming interface for software-defined quantum networks, inspired by frameworks like Frenetic, along with a holistic simulator to evaluate quantum network protocols at scale. Our work explores the design space of realistic quantum network protocols that remain robust as physical conditions change.
Our ICNP 2024 work introduces QuARC (Quantum Adaptive Routing using Clusters), a clustering-based entanglement routing protocol. QuARC periodically reconfigures the network into clusters using topology information and local measurements, without requiring advance knowledge of physical parameters. Its adaptive, multipath routing supports high-throughput entanglement distribution without starvation as network sizes and physical conditions change.
Our complementary work, A Control Protocol for Wide-Area Quantum Links, develops an optimization framework for maintaining high-quality, high-rate entanglement distribution over long distances. The protocol responds to time-varying noise by adaptively tuning hardware-level parameters through control-theoretic decision processes. A trace-driven evaluation using data from a 62 km over-air fiber demonstrates how software-based adaptation can improve quantum link performance. This work will appear at SIGMETRICS 2027.
Publications:
Efficient Routing on Quantum Networks using Adaptive Clustering. Connor Clayton, Xiaodi Wu, and Bobby Bhattacharjee. 32nd IEEE International Conference on Network Protocols (ICNP 2024). arXiv DOI
A Control Protocol for Wide-Area Quantum Links. Connor Clayton, Cory Nunn, Wayne McKenzie, Quinn Carmack, Anne Marie Richards, Xiaodi Wu, and Bobby Bhattacharjee. To appear in Proceedings of the ACM on Measurement and Analysis of Computer Systems (POMACS); SIGMETRICS 2027. NIST arXiv version
Software Foundation of Quantum Computing
Formally Verified Software Tool-chain for Quantum Computing
The complexity of quantum computing and the limitations of near-term quantum devices make the development of sophisticated quantum algorithms and clever optimizations prone to mistakes. This calls for verifying every stage of quantum computation, from the software tools used to generate quantum circuits to the architecture and system design.
We are inspired by formal methods applied in safety-critical domains to ensure the correctness of code by construction, especially in the example of CompCert (a C compiler written and proved correct in Coq) and the NSF project of deep specification (a project to develop specifications of software toolchains to prove end-to-end correctness of whole systems). A verified quantum computing stack would ensure that each level of quantum computation is implemented according to its specifications and that the final system is correct, which would have a wide practical impact. This approach is especially appealing to quantum computing since alternative software assurance techniques are very limited due to the substantial expense involved in the quantum setting. As an important first step, we have built a proved-correct optimizing compiler for quantum algorithms to optimize the gate count, the depth of circuits, etc., while adhering to any architectural constraints. To that end, we developed an infrastructure for reasoning about quantum programs/operations in Coq, which is so expressive and flexible that we recently accomplished an end-to-end implementation of Shor's algorithm, with both classical and quantum parts as well as a formal correctness proof of everything, in Coq.
Publications:
A Formally Certified End-to-End Implementation of Shor's Factorization Algorithm. Yuxiang Peng, Kesha Hietala, Runzhou Tao, Liyi Li, Robert Rand, Michael Hicks, and Xiaodi Wu. Proceedings of the National Academy of Sciences 120(21), e2218775120 (2023). arXiv Code DOI
Verified Compilation of Quantum Oracles. Liyi Li, Finn Voichick, Kesha Hietala, Yuxiang Peng, Xiaodi Wu, and Michael Hicks. Proceedings of the ACM on Programming Languages 6 (OOPSLA2), 589–615 (2022). arXiv Code DOI
A Verified Optimizer for Quantum Circuits. Kesha Hietala, Robert Rand, Liyi Li, Shih-Han Hung, Xiaodi Wu, Michael Hicks. ACM Transactions on Programming Languages and Systems 45(3), Article 18, 1–35 (2023). Earlier published as a distinguished paper at POPL 2021. arXiv Code Journal
Verified Optimization in a Quantum Intermediate Representation. Kesha Hietala, Robert Rand, Shih-Han Hung, Xiaodi Wu, and Michael Hicks. Preprint, 2019. Workshop extended abstract: Quantum Physics and Logic (QPL) 2019. arXiv QPL abstract
Quantum Program Analysis & Verification
Quantum programs are error-prone and their verification is challenging due to the limitations of standard software assurance techniques in the quantum setting. My research investigates the verification of quantum programs via their static analysis with the help of quantum Hoare logic. A prominent approach for program verification is to generate invariants and inductive assertions, which is already a highly non-trivial task even classically. I made the first proposal of quantum invariants, showed how to generate them using semidefinite programs (SDPs), and demonstrated their use in quantum program verification.
We also investigate the algebraic reasoning of quantum programs inspired by the success of classical program analysis based on Kleene algebra. One prominent example is the famous Kleene Algebra with Tests (KAT), which has furnished both theoretical insights and practical tools. A few key features of KAT, including the idempotent law and useful properties of classical tests, however, fail to hold in the context of quantum programs due to their unique quantum features, especially in branching. We propose the Non-idempotent Kleene Algebra (NKA) as a natural alternative and identify complete and sound semantic models for NKA as well as their appropriate quantum interpretations. This enables algebraic proofs in NKA of quantum compiler optimizations and the normal form of quantum while-programs.
Publications:
Qafny: A Quantum-Program Verifier. Liyi Li, Mingwei Zhu, Rance Cleaveland, Alexander Nicolellis, Yi Lee, Le Chang, and Xiaodi Wu. ECOOP 2024, LIPIcs 313, 24:1–24:31. arXiv Code DOI
Algebraic Reasoning of Quantum Programs via Non-Idempotent Kleene Algebra. Yuxiang Peng, Mingsheng Ying, and Xiaodi Wu. 43rd ACM SIGPLAN PLDI 2022. arXiv Proceedings
On the Theory and Practice of Invariant-based Verification of Quantum Programs. Shih-Han Hung, Yuxiang Peng, Xin Wang, Shaopeng Zhu, and Xiaodi Wu. Preprint, 2019. Preprint
Invariants of Quantum Programs: Characterisations and Generation. Mingsheng Ying, Shenggang Ying, and Xiaodi Wu 44th ACM SIGPLAN POPL 2017. Preprint Proceedings
Quantum Applications in Optimization and Machine Learning
Provable Quantum Advantages for Optimization and Machine Learning
My recent research aims to understand the landscape of provable quantum advantages in optimization and machine learning, a major targeted domain of quantum applications. To that end, I have developed quantum algorithms with polynomial speed-ups over classical ones for semidefinite programs (SDPs), general convex optimization, training linear and kernelized classifiers, and estimating volumes of high-dimensional convex bodies. My algorithms also hint at possible exponential quantum speed-ups when using quantum data as inputs/outputs of SDPs and the principal component analysis problem.
Publications:
Sublinear Classical and Quantum Algorithms for General Matrix Games. Tongyang Li, Chunhao Wang, Shouvanik Chakrabarti, and Xiaodi Wu. 35th AAAI Conference on Artificial Intelligence (AAAI 2021). arXiv Proceedings
Quantum algorithm for estimating volumes of convex bodies. Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, Shih-Han Hung, Chunhao Wang, and Xiaodi Wu. ACM Transactions on Quantum Computing 4(3), Article 20, 1–60 (2023). Workshop presentation: QIP 2020 (single-track talk). arXiv Journal
Sublinear quantum algorithms for training linear and kernel-based classifiers. Tongyang Li, Shouvanik Chakrabarti, and Xiaodi Wu 36th International Conference on Machine Learning (ICML 2019). arXiv Proceedings
Quantum SDP Solvers: Large Speed-ups, Optimality, and Applications to Quantum Learning. Fernando G. S. L. Brandao, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu ICALP 2019, LIPIcs 132, 27:1–27:14. Workshop presentation: QIP 2019. arXiv Proceedings
Quantum algorithms and lower bounds for convex optimization. Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu. Quantum 4, 221 (2020). Workshop presentation: QIP 2019. arXiv Journal
Variational Quantum Methods
Quantum neural networks (i.e., parameterized quantum circuits) are important and promising candidates for applications of quantum machine learning. My research aims to conduct a theory-guided comprehensive investigation in this regard, including functionality (e.g., representation learning, generative models), training methods (e.g., landscape characterization, under/over-parameterization), and separation between quantum and classical neural networks.
Publications:
A Convergence Theory for Over-parameterized Variational Quantum Eigensolvers. Xuchen You, Shouvanik Chakrabarti, and Xiaodi Wu. Preprint, 2022. Workshop presentation: QIP 2023 (contributed talk). arXiv
Analyzing Convergence in Quantum Neural Networks: Deviations from Neural Tangent Kernels. Xuchen You, Shouvanik Chakrabarti, Boyang Chen and Xiaodi Wu. ICML 2023, Proceedings of Machine Learning Research 202, 40199–40224. arXiv Proceedings
Two-way Separations in Expressivity between Quantum Neural Networks and Feed-forward ReLU Networks. Shouvanik Chakrabarti and Xiaodi Wu Preprint, 2021.
Exponentially Many Local Minima in Quantum Neural Networks. Xuchen You and Xiaodi Wu. 38th International Conference on Machine Learning (ICML 2021). arXiv Proceedings
Quantum Wasserstein Generative Adversarial Networks. Shouvanik Chakrabarti*, Yiming Huang*, Tongyang Li, Soheil Feizi, and Xiaodi Wu. 33rd Annual Conference on Neural Information Processing Systems (NeurIPS 2019). arXiv Proceedings
Differentiable Quantum Programming Languages & Quantum Neuro-Symbolic Applications
Inspired by the emerging paradigm shift from deep learning toward differentiable programming promoted by prominent classical machine learning researchers, I have initiated the formalization of differentiable quantum programming. This project provides automatic differentiation techniques for quantum programs, in particular the possibility of using quantum programs to compute the gradients of another quantum program, to support scalable gradient-based training in quantum machine learning. It also opens the possibility of designing novel quantum “neuro-symbolic” applications that combine program features/synthesis with simple neural networks. The study of their classical counterpart, although still in its infancy, has already shown great potential and promise over conventional neural networks. We demonstrated, for the first time, one such example for quantum machine learning.
Publications:
Differentiable Quantum Computing for Large-scale Linear Control. Connor Clayton*, Jiaqi Leng*, Gengzhi Yang*, Yi-Ling Qiao, Ming C. Lin, and Xiaodi Wu. Advances in Neural Information Processing Systems 37 (NeurIPS 2024). arXiv Proceedings
Differentiable Quantum Programming with Unbounded Loops. Wang Fang, Mingsheng Ying and Xiaodi Wu. ACM Transactions on Software Engineering and Methodology 33(1), Article 19, 1–63 (2024). First published online in November 2023. arXiv DOI
Differentiable Analog Quantum Computing for Optimization and Control. Jiaqi Leng*, Yuxiang Peng*, Yi-Ling Qiao*, Ming C. Lin, and Xiaodi Wu. Advances in Neural Information Processing Systems 35 (NeurIPS 2022). arXiv Code Proceedings
On the Principles of Differentiable Quantum Programming Languages. Shaopeng Zhu, Shih-Han Hung, Shouvanik Chakrabarti, and Xiaodi Wu. 41st ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2020). arXiv Code Proceedings
Quantum Algorithms for Property Testing
Another well-motivated topic is the property testing of quantum and classical distributions. I have closed a long-standing gap between the upper and lower bounds on the sample complexity of reconstructing quantum states, known as quantum tomography, which is a fundamental step to verify the preparation of the experimental setup. I also demonstrated the quantum speed-up in estimating the Shannon and Rényi entropies of classical distributions.
Publications:
Quantum query complexity of entropy estimation. Tongyang Li and Xiaodi Wu IEEE Transactions on Information Theory 65(5), 2899–2921 (2019). arXiv Journal
Sample-optimal tomography of quantum states. Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, Nengkun Yu IEEE Transactions on Information Theory 63(9), 5628–5641 (2017). Conference version: STOC 2016, 913–925. Workshop presentation: QIP 2016. arXiv Journal STOC proceedings
Quantum Architecture Engineering for NISQ era
Near-term quantum computers are likely to have very restricted hardware resources, where precisely controllable qubits are expensive, error-prone, and scarce. Therefore, application designers for such noisy intermediate-scale quantum (NISQ) computers are forced to investigate the best balance of trade-offs among a large number of (potentially heterogeneous) factors specific to the targeted application and quantum hardware.
Noise-Analysis of Quantum Applications
We believe that one way to attack these problems is to set aside a one-size-fits-all approach to fault tolerance and instead consider elevating the question of errors and related architecture-specific resource optimization to the level of the programming language and algorithm design. In particular, inspired by techniques in approximate computing that optimize computation on unreliable classical hardware, we've built formal semantics and a logic for reasoning about reliability in the presence of noise in quantum computation.
Publications:
Quantitative Robustness Analysis of Quantum Programs. Shih-Han Hung, Kesha Hietala, Shaopeng Zhu, Mingsheng Ying, Michael Hicks, and Xiaodi Wu. Proceedings of the ACM on Programming Languages 3(POPL), Article 31, 1–29 (2019). arXiv Publication
Meta-Programming Framework for Automating NISQ Application Design
We propose Meta Quantum Circuits with Constraints (MQCC), a meta-programming framework for quantum programs, to help balance trade-offs in NISQ application design. Designers express their application as a succinct collection of normal quantum circuits stitched together by a set of meta-level choice variables, whose values are constrained according to a programmable set of quantitative optimization criteria. MQCC's compiler automatically generates the appropriate constraints, hands them to a solver (e.g., a Satisfiability Modulo Theories (SMT) solver), and from the solution produces an optimized, runnable program. We demonstrate MQCC's expressiveness through an extensive case study, demonstrating that ideas from previous examples of NISQ application design – such as multi-programming, cost-effective uncomputation, and crosstalk mitigation, as well as their combination – can be readily implemented in MQCC, and produce comparable results.
Publications:
Automating NISQ Application Design with Meta Quantum Circuits with Constraints (MQCC). Haowei Deng, Yuxiang Peng, Michael Hicks, and Xiaodi Wu. ACM Transactions on Quantum Computing 4(3), Article 16, 1–29 (2023). Code Journal Published PDF
Leveraging Small Quantum Machines for NISQ Applications
My pioneering theoretical proposal to decompose large quantum circuits into smaller, manageable circuits for execution on quantum machines has now been adopted as a foundational technique by industry leaders such as IBM and AWS. Now known as “circuit knitting,” this approach is playing a key role in the roadmaps of major companies to scale quantum applications over the next decade.
Cryptography & Security in the Quantum Regime
Tamper-resilient Cryptography under Physical Assumptions
Devices, classical or quantum, are subject to tampering in cryptographic settings, especially due to the proliferation of side-channel attacks. These attacks exploit the fact that devices leak information to the outside world not just through input-output interaction, but through physical characteristics of computation such as power consumption, timing, and electromagnetic radiation. Research on this topic explores two possible solutions to protect cryptographic systems from (quantum) side-channel attacks.
Device-independent Cryptography: In this setting, none of the devices can be a priori trusted: security is based solely on simple tests performed by honest users on the input-output behavior of their devices. The security analysis guarantees that any set of devices meeting reasonable physical assumptions (e.g., spatial separations of devices that prohibit mutual communication) and conducting an acceptable interaction will lead to a secure outcome, regardless of the actual process inside the devices. My research focuses on generating uniform random bits in this setting under minimal assumptions. Check the recent review in Nature (Certified randomness in quantum physics) about this research direction and my work.
Leakage-resilient Cryptography: Modern computing environments, such as cloud computing, where computation no longer takes place on private machines under our control, expose many classical cryptographic systems to side-channel attacks. The leakage can be quantum. Collecting and storing quantum side information is technically much less challenging than building fully-fledged quantum computers, and could become realistic in the near future. My research focuses on studying the role of quantum side information in both information-theoretical and computational settings. In a recent result, I initiated the study of computational notions of entropy in the quantum setting and developed the first quantum leakage-resilient cryptographic protocol.
Both device-independent and leakage-resilient cryptography can be viewed as tamper-resilient cryptography under physical assumptions. My future plan is to bring these cryptographic designs closer to practice, with better efficiency and broader functionality.
Publications:
Computational Notions of Quantum Min-Entropy. Yi-Hsiu Chen, Kai-Min Chung, Ching-Yi Lai, Salil P. Vadhan, and Xiaodi Wu Preprint, 2017. Presented at the 7th International Conference on Quantum Cryptography (QCrypt 2017). arXiv
General randomness amplification with non-signaling security. Kai-Min Chung, Yaoyun Shi, and Xiaodi Wu Preprint, 2017. Workshop presentation: QIP 2017. Preprint
Multi-Source Randomness Extractors Against Quantum Side Information, and their Applications. Kai-Min Chung, Xin Li, and Xiaodi Wu Preprint, 2014. arXiv
Physical Randomness Extractors: Generating Random Numbers with Minimal Assumptions. Kai-Min Chung, Yaoyun Shi, and Xiaodi Wu Preprint, 2014. Workshop presentation: QIP 2014 (plenary talk). arXiv Simons talk QCrypt 2014 talk
(Practical) Delegation and Verification of Quantum Computation
In a recent breakthrough, Mahadev constructed a classical verification of quantum computation (CVQC) protocol for a classical client to delegate decision problems in BQP to an untrusted quantum prover under computational assumptions. We explore further the feasibility of CVQC with the more general sampling problems in BQP and with the desirable blindness property, and contribute affirmative solutions to both. We also investigate the lightweight verification of quantum supremacy, where all existing protocols, either based on classical simulation or public-key quantum cryptography, are too expensive to serve the purpose of practical verification. We propose a circuit-obfuscation-based verification scheme for quantum supremacy that is scalable and has some complexity-theoretic support based on the quantum minimum equivalent circuit problem (QMECP). We also implement a prototype of our circuit obfuscator which has the desired empirical performance against attacks from the off-the-shelf tools tested.
Publications:
A Scalable Classical Verification reveals the Gap of the State-Of-The-Art Gaussian Boson Sampling Experiments. Yufan Zheng, Yingkang Cao, and Xiaodi Wu. Preprint, 2023. APS abstract
Constant-round Blind Classical Verification of Quantum Sampling. Kai-Min Chung, Yi Lee, Han-Hsuan Lin, and Xiaodi Wu. Eurocrypt 2022. arXiv Proceedings
Scalable Verification of Quantum Supremacy based on Circuit Obfuscation. Shouvanik Chakrabarti, Chi-Ning Chou, Kai-Min Chung, and Xiaodi Wu. Preprint, 2021. Code
Mechanized and Automated Security Analysis of Cryptographic Systems under Quantum Attacks
The advent of quantum computing has introduced the risk of quantum attacks on modern communication security techniques. Protecting today’s sensitive information from future threats requires deploying robust defenses soon. However, post-quantum security analysis is complex, error-prone, and requires specialized expertise, delaying practical adoption.
To address this, I develop formal methods for automated security analysis of cryptographic systems against quantum attacks, automating expert analysis and facilitating deployment. For instance, we extended EasyCrypt to evaluate quantum adversaries (CCS’21) and formally certify NIST’s post-quantum standardization finalists. Notably, during this process, we uncovered a critical flaw in the published security proof of the Dilithium signature scheme (a NIST finalist) and provided a theoretical and certified fix (CRYPTO’23).
Publications:
Fixing and Mechanizing the Security Proof of Fiat-Shamir with Aborts and Dilithium. Manuel Barbosa, Gilles Barthe, Christian Doczkal, Jelle Don, Serge Fehr, Benjamin Grégoire, Yu-Hsuan Huang, Andreas Hülsing, Yi Lee, and Xiaodi Wu. Advances in Cryptology – CRYPTO 2023, Part V, LNCS 14085, 358–389. IACR ePrint DOI
EasyPQC: Verifying Post-Quantum Cryptography. Manuel Barbosa, Gilles Barthe, Xiong Fan, Benjamin Grégoire, Shih-Han Hung, Jonathan Katz, Pierre-Yves Strub, Xiaodi Wu, and Li Zhou. ACM SIGSAC Conference on Computer and Communications Security (CCS 2021), 2564–2586. IACR ePrint DOI
Quantum Sensing Networks
The demand for highly accurate position and time information, provided by localization and synchronization methods, respectively, is growing rapidly. However, classical localization and synchronization methods are approaching their limits. Utilizing quantum properties promises to push these boundaries beyond classical limitations and provide unprecedented accuracy. We aim to develop theoretical and practical methodologies for the design and analysis of quantum localization and synchronization networks. These methodologies consist of statistical models and distributed algorithms to harness quantum phenomena for beyond-classical localization and synchronization.
Publications:
Earlier Theoretical Studies in Quantum Information and Computation
Entanglement, Quantum Correlations, and Sum-of-Squares
Research on this topic studies many aspects of two key quantum features, entanglement and non-locality. I attack this topic by exploring a surprising connection between quantum information and the sum-of-squares (SOS) proof in approximation algorithms and the famous Unique Games Conjecture (UGC). This connection allows technical advances in one field to inform the other. Specific problems that I am working on include the characterization of separable (unentangled) states, the complexity of quantum Merlin-Arthur games with unentangled provers (QMA(2)), the possibility of a quantum-inspired approach to attack the UGC.
Publications:
Limitations of semidefinite programs for separable states and entangled games. Aram Harrow, Anand Natarajan, Xiaodi Wu Communications in Mathematical Physics 366(2), 423–468 (2019). Workshop presentation: QIP 2017. arXiv Journal
Tight SoS-degree bounds for approximate Nash equilibria. Aram Harrow, Anand Natarajan, Xiaodi Wu Computational Complexity Conference (CCC) 2016. Proceedings
An improved semidefinite programming hierarchy for testing entanglement. Aram Harrow, Anand Natarajan, Xiaodi Wu Communications in Mathematical Physics, June 2017, Volume 352, Issue 3, pp 881--904. arXiv Journal
Epsilon-net method for optimizations over separable states. Yaoyun Shi and Xiaodi Wu Theoretical Computer Science 598, 51–63 (2015). Conference version: ICALP 2012. Workshop presentation: QIP 2012 (contributed talk). arXiv Proceedings Journal
Quantum Computational Complexity
Interactive proof systems have been a central model in complexity theory with applications ranging from the PCP theorem in the hardness of approximation to cryptography. These systems study problems with efficiently verifiable proofs via interactions between a polynomial-time verifier and all-powerful provers, where the verifier determines the validity of the proofs. My main contribution on this topic is the development of the Equilibrium Value Method to obtain space-efficient simulations of quantum interactive proof systems, including QIP=PSPACE, QRG(2)=PSPACE. Recently, I have been working on the quantum variant of the PCP theorem in the interactive proof setting. As a concrete first step, I have obtained a parallel repetition result for entangled k-player games.
Publications:
Parallel repetition for entangled k-player games via fast quantum search. Kai-Min Chung, Xiaodi Wu and Henry Yuen Computational Complexity Conference (CCC) 2015. arXiv Proceedings PDF Proceedings DOI
Epsilon-net method for optimizations over separable states. Yaoyun Shi and Xiaodi Wu Theoretical Computer Science 598, 51–63 (2015). Conference version: ICALP 2012. Workshop presentation: QIP 2012 (contributed talk). arXiv Proceedings Journal
Parallel Approximation of Min-Max Problems. Gus Gutoski and Xiaodi Wu Computational Complexity 22(2), 385–428 (2013), special issue of CCC 2012. Conference version: CCC 2012. Workshop presentation: QIP 2012 (featured talk). arXiv Proceedings Journal
Equilibrium Value Method for the proof of QIP=PSPACE. Xiaodi Wu Preprint, 2010. arXiv