Abstract: This talk will be split into two parts. First, we study classical oracle separations for the quantum-classical polynomial hierarchy, QCPH, which is the class of languages solvable by a constant number of alternating classical quantifiers followed by a quantum verifier. Our main result is that QCPH is infinite relative to a random oracle (previously, this was not even known relative to any oracle). We further prove that higher levels of PH are not contained in lower levels of QCPH relative to a random oracle; this is a strengthening of the somewhat recent result that PH is infinite relative to a random oracle (Rossman, Servedio, and Tan 2016). The oracle separation requires lower bounding a certain type of low-depth alternating circuit with some quantum gates. To establish this, we give a new switching lemma for quantum algorithms which may be of independent interest.

Second, we study oracle separations in the quantum oracle model. In recent years, the quantum oracle model has found a lot of use in showing oracle separations between complexity classes and cryptographic primitives. It is generally assumed that proof techniques that do not relativize with respect to quantum oracles will also not relativize with respect to classical oracles. We show that this is not the case: specifically, we show that there is a quantum oracle problem that is contained in the class QMA, but not in a class we call polyQCPH. The class polyQCPH is equal to PSPACE with respect to classical oracles, and it is a well-known result that QMA is contained in PSPACE (also with respect to classical oracles). We believe our findings show the need for some caution when using these non-standard oracle models, particularly when showing separations between quantum and classical resources.

This talk is based on joint works with Shalev Ben-David and Srijita Kundu.

Abstract: The Learning with Errors (LWE) problem has served as a security foundation for numerous cryptographic primitives. Not only is it the most prominent hardness assumption for post-quantum cryptography, but its algebraic simplicity enables the design of primitives with advanced functionalities. Thus, it is crucial to analyse the quantum fine-grained hardness of this problem.

In this talk, our objective is to cover a few ideas in the quest for quantum algorithms for LWE. We will first look at the Dihedral Hidden Subgroup / Dihedral Coset problem (DCP), and Kuperberg’s sieving technique that gives a subexponential algorithm for this problem. We will then see Regev’s reduction from LWE to a faulty version of DCP. The faulty nature of this reduction hampers us from having a subexponential algorithm for LWE. Next, we will establish the equivalence of LWE to an extrapolated version of DCP (EDCP).

We will then examine recent ventures in defining quantum variants of LWE. Specifically, we will define S|LWE>, and then look at a subexponential time algorithm solving S|LWE> for certain amplitudes. However, we only manage to reduce an LWE instance to an S|LWE>-like instance where the phase of the amplitude is unknown. This again seems to pose a barrier against a subexponential algorithm for LWE.

Abstract: In recent years, semidefinite programming has found numerous applications in computer science, ranging from approximation algorithms for Max-Cut and other graph partitioning problems to improved performance bounds for error-correcting codes.

In this talk, I will first introduce the formalism of linear and semidefinite programming and then discuss several cryptographic primitives—such as coin flipping, oblivious transfer, and bit commitment—that serve as building blocks or subroutines for many cryptographic protocols.

Subsequently, I will review known bounds on the information-theoretic (unconditional) security of these tasks in both classical and quantum settings, using analyses based on semidefinite programming. Finally, I will present a switching framework [Bansal and Sikora, 2025] that leverages stochastic semidefinite programming to construct secure protocols from insecure ones.

Abstract: In the "search with wildcards'' problem [Ambainis, Montanaro, Quantum Inf.~Comput.'14], one's goal is to learn an unknown bit-string x in {-1,1}^n. An algorithm may, at unit cost, test equality of any subset of the hidden string with a string of its choice. Ambainis and Montanaro showed a quantum algorithm of cost O(sqrt{n} log n) and a near-matching lower bound of Omega(sqrt{n}). Belovs [Comput.~Comp.'15] subsequently showed a tight O(sqrt{n}) upper bound.

We consider a natural generalization of this problem, parametrized by a subset Q of 2^{[n]}, where an algorithm may test whether x_S = b for an arbitrary S in Q and b in {-1,1}^S of its choice, at unit cost. We show tight bounds for various choices of Q, such as sets of bounded size, contiguous blocks, prefixes, and only the full set. In particular, setting Q = 2^{[n]} recovers the tight bounds mentioned above.

All of these results are derived using a framework that we develop. We show, using the primal adversary bound, that the quantum query complexity of learning x is characterized, up to a constant factor, by a particular abstract analytic optimization program. Based on joint work with Arjan Cornelissen, Subhasree Patro, Nithish Raja, and Swagato Sanyal.

Abstract: Isogenies have emerged as a viable alternative to lattice for post-quantum cryptography over the past 20 years. However, due to the uniquely complex underlying mathematical features and security/efficiency properties, the landscape of isogeny-based cryptography has remained somewhat limited and inaccessible to the wider cryptographic community. Additionally, building new cryptographic applications from isogenies has been a potentially tedious and time-consuming task.

In this talk, I will present overviews of two frameworks for isogeny-based cryptography, namely “cryptographic group actions” and “cryptographic forensic categories”. These frameworks enable viewing isogeny-based cryptography through the lens of abstract and easy-to-understand algebraic structures combined with simple cryptographic hardness assumptions. I will showcase some applications of these frameworks in: (i) enabling simplified expositions of well-known cryptographic constructions from isogenies (e.g., CSIDH-based public-key encryption and the SQIsign family of digital signatures), and (ii) realizing new (plausibly) post-quantum instances of advanced cryptographic primitives from isogenies. I will hope to demonstrate the simplicity and usability of these frameworks for isogeny non-experts. Along the way, I will also talk about some hard problems that form the basis of isogeny-based cryptography, and their classical/quantum hardness as of today.

No prior background in either cryptography or quantum computing will be necessary to follow the talk.

Abstract: A polynomial p(x) is said to approximate a Boolean function f:{0,1}^n -> {0,1} if |f(x)-p(x)| <= 1/3 for all x \in {0,1}^n. The approximate degree of f, denoted adeg(f), is defined to be the minimal degree of an approximating polynomial for f. It was introduced roughly 30 years back in a seminal work of Nisan and Szegedy (Computational Complexity 1994). Since then it has become a powerful and versatile tool in theoretical computer science finding spectacular applications in circuit complexity, quantum query complexity, communication complexity, computational learning, and differential privacy, to name a few.

This talk will be about an important problem about approximate degree -- Does it compose? Formally, for any two Boolean functions f and g, the composed function f o g is defined as, f o g (x_1, ... , x_n) = f(g(x_1), ..., g(x_n)), where x_i \in {0,1}^m. In a beautiful and significant work, Sherstov (Theory of Computing 2013) showed that adeg(f o g) = O(adeg(f)adeg(g)). The approximate degree composition problem posits that this upper bound is tight. That is, adeg(f o g) = \Omega(adeg(f) adeg(g)) for all f and g.

I will survey the current state of progress, including its connections to quantum algorithms.

Qiksit has been a popular software stack for quantum computing, with open surveys indicating 70% of quantum developers across the world using it for a few years now. In this talk, we will discuss the different layers of Qiskit, while exploring some of the key algorithms behind its functioning. We will start with the algorithms used in the core modules which perform efficient compilation of quantum programs. We will then move up the stack to cover a class of sampling-based algorithms that leverage hybrid quantum computing - classical supercomputing infrastructure and provide the state-of-the-art results for many applications of quantum computing. All these have accompanying open-source code in http://github.com/Qiskit to build on them for your research.