How to construct quantum Markov chains
Speaker: Chi-Fang (Anthony) Chen (Simons, UC Berkeley)
Classical Markov chains and Monte Carlo methods have driven major advances in statistical physics, probability, and modern computation. [cite_start]In this talk, I will present a general construction of quantum Markov chains that provides both a rigorous quantum algorithmic framework for sampling Gibbs states and a physically consistent dynamical model of thermalization in many-body quantum systems. [cite: 26]
QuantumBoost: A lazy, yet fast, quantum algorithm for learning with weak hypotheses
Speaker: Yanlin Chen (UMD and QuICS)
The technique of combining multiple votes to enhance the quality of a decision is the core of boosting algorithms in machine learning. In particular, boosting provably increases decision quality by combining multiple weak learners-hypotheses that are only slightly better than random guessing-into a single strong learner that classifies data well. There exist various versions of boosting algorithms, which we improve upon through the introduction of QuantumBoost. Inspired by classical work by Barak, Hardt and Kale, our QuantumBoost algorithm achieves the best known runtime over other boosting methods through two innovations. First, it uses a quantum algorithm to compute approximate Bregman projections faster. Second, it combines this with a lazy projection strategy, a technique from convex optimization where projections are performed infrequently rather than every iteration. [cite_start]To our knowledge, QuantumBoost is the first algorithm, classical or quantum, to successfully adopt a lazy projection strategy in the context of boosting. [cite: 4, 5, 6, 7, 8, 9]
Strong random unitaries and fast scrambling
Speaker: Hsin-Yuan Huang (Caltech and Google Quantum AI)
Understanding how fast physical systems can resemble Haar-random unitaries is a fundamental question in physics. Many experiments of interest in quantum gravity and many-body physics, including the butterfly effect in quantum information scrambling and the Hayden-Preskill thought experiment, involve queries to a random unitary U alongside its inverse U^†, conjugate U^*, and transpose U^T. However, conventional notions of approximate unitary designs and pseudorandom unitaries (PRUs) fail to capture these experiments. In this work, we introduce and construct strong unitary designs and strong PRUs that remain robust under all such queries. Our constructions achieve the optimal circuit depth of O(log n) for systems of n qubits. We further show that strong unitary designs can form in circuit depth O(log^2 n) in circuits composed of independent two-qubit Haar-random gates, and that strong PRUs can form in circuit depth poly(log n) in circuits with no ancilla qubits. [cite_start]Our results provide an operational proof of the fast scrambling conjecture from black hole physics: every observable feature of the fastest scrambling quantum systems reproduces Haar-random behavior at logarithmic times. [cite: 1, 2, 3]
On the Limitations of Pseudorandom Unitaries
Speaker: Yao-Ting Lin (UCSB)
Pseudorandom unitaries (PRUs), one of the key quantum pseudorandom notions, are efficiently computable unitaries that are computationally indistinguishable from Haar random unitaries. While there is evidence to believe that PRUs are weaker than one-way functions, so far its relationship with other quantum cryptographic primitives (that are plausibly weaker than one-way functions) has not been fully established. In this work, we focus on quantum cryptographic primitives with classical communication, referred to as QCCC primitives. Our main result shows that QCCC bit commitments and QCCC key agreement, cannot be constructed from pseudorandom unitaries in a black-box manner. Our core technical contribution is to show (in a variety of settings) the difficulty of distinguishing identical versus independent Haar unitaries by separable channels. Our result strictly improves upon prior works which studied similar problems in the context of learning theory [Anshu, Landau, Liu, STOC 2022] and cryptography [Ananth, Gulati, Lin, TCC 2024]. [cite_start]*Based on joint work with Prabhanjan Ananth and Aditya Gulati, to appear in TCC 2025. [cite: 20, 21, 22, 23, 24, 25]
Lower Bounds on Inner-Product Functional Encryption from All-or-Nothing Encryption Primitives
Speaker: Wei-Kai Lin (University of Virginia)
Functional encryptions (FE) provide fine-grained access control over encrypted data. The class of functions supported by an FE scheme can vary widely, from all circuits to much simpler functions, such as inner products. Particularly, FE for all circuits is extremely powerful and can be existentially equivalent to indistinguishability obfuscation. In contrast, FE for inner products (IPFE) can be based on standard assumptions, such as DDH or LWE. Do FEs fundamentally differ from other fancy encryption schemes, such as IBE, ABE, or FHE? In this talk, we separate FEs from the other fancy encryptions. That is, there is no IPFE constructed using ABE and FHE in the “almost” black-box way. Since inner product is a weak class of functions, this makes the impossibility stronger. The separation holds for (IP)FEs that are secure against an unbounded number of colluded functional keys. We additionally separate IPFEs from attribute-hiding predicate encryptions. [cite_start]This is a joint work with Jinye He and Shiyu Li. [cite: 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
Fully Homomorphic Encryption with Efficient Public Verification
Speaker: Miryam Huang (USC)
Explicit Lossless Vertex Expanders
Speaker: Jun-Ting (Tim) Hsieh (MIT)
Lattice-Based Post-Quantum iO from Circular Security with Random Opening Assumption
Speaker: Yao Ching Hsieh (University of Washington)
Indistinguishability obfuscation (iO) stands out as a powerful cryptographic primitive but remains notoriously difficult to realize under simple-to-state, post-quantum assumptions. Recent works have proposed lattice-inspired iO constructions backed by new “LWE-with-hints” assumptions, which posit that certain distributions of LWE samples retain security despite auxiliary information. However, subsequent cryptanalysis has revealed structural vulnerabilities in these assumptions. In this talk, I will talk about our recent attempt on overcoming key vulnerabilities in prior LWE-with-hint formulations. We introduce a new assumption, the Circular Security with Random Opening (CRO) assumption, featuring two critical properties: (1) the hint distribution is marginally uniform, and (2) natural uses of the hint do not give any noise leakage. These properties rule out important classes of attack strategies, including those that have broken earlier assumptions. [cite_start]Therefore, our new lattice-based assumption for iO provides a qualitatively different target for cryptanalysis compared to existing assumptions. [cite: 27, 28, 29, 30, 31, 32]
A Lower Bound on the Trace Norm of Boolean Matrices and Its Applications
Speaker: Tsun Ming (Ben) Cheung (Institute of Information Science, Academia Sinica)
Fiat-Shamir Transformation of Special-Sound Interactive Proofs
Speaker: Er-Cheng Tang (University of Washington)
On cryptography and distribution verification, with application to quantum advantage.
Speaker: Taiga Hiroka (Foxconn Research)
