We study unitary property testing, where a quantum algorithm is given query access to a black-box unitary and has to decide whether it satisfies some property. In addition to containing the standard quantum query complexity model (where the unitary encodes a binary string) as a special case, this model contains "inherently quantum" problems that have no classical analogue. Characterizing the query complexity of these problems requires new algorithmic techniques and lower bound methods. Our main contribution is a generalized polynomial method for unitary property testing problems. By leveraging connections with invariant theory, we apply this method to obtain lower bounds on problems such as determining recurrence times of unitaries, approximating the dimension of a marked subspace, and approximating the entanglement entropy of a marked state. We also present a unitary property testing-based approach towards an oracle separation between $\mathsf{QMA}$ and $\mathsf{QMA(2)}$, a long standing question in quantum complexity theory.
We study unitary property testing, where a quantum algorithm is given query access to a black-box unitary and has to decide whether it satisfies some property. In addition to containing the standard quantum query complexity model (where the unitary encodes a binary string) as a special case, this model contains "inherently quantum" problems that have no classical analogue. Characterizing the query complexity of these problems requires new algorithmic techniques and lower bound methods. Our main contribution is a generalized polynomial method for unitary property testing problems. By leveraging connections with invariant theory, we apply this method to obtain lower bounds on problems such as determining recurrence times of unitaries, approximating the dimension of a marked subspace, and approximating the entanglement entropy of a marked state. We also present a unitary property testing-based approach towards an oracle separation between QMA and QMA(2), a long standing question in quantum complexity theory.
Algebraic methods have become a powerful tool for analyzing the complexity of various computational models, including low-depth circuits, algebraic proofs, and quantum query algorithms. In particular, the complexity of computing a function in these models is related to whether or not the function admits a low-degree polynomial approximation. In this thesis, we present two novel applications of algebraic methods in computational complexity theory. In the first part of the thesis, we study unitary property testing, where a quantum algorithm is given query access to a black-box unitary and has to decide whether or not it satisfies some property. In addition to containing the classical query complexity model as a special case, this model also contains "inherently quantum" problems that have no classical analogue. Our main contribution is a generalized polynomial method for analyzing the complexity of unitary property testing problems. By leveraging connections with invariant theory, we apply this method to obtain lower bounds on problems such as determining recurrence times of unitaries, approximating the dimension of a subspace, and approximating the entanglement entropy of a state. We also present a candidate problem towards an oracle separation of QMA and QMA(2), a long standing open question in quantum complexity theory. In the second part of the thesis, we study the tensor isomorphism problem (TI), which has recently emerged as having connections to multiple areas of research, including quantum information theory, post-quantum cryptography, and computational algebra. However, the current best upper bound is essentially the brute force algorithm. Being an algebraic problem, the study of tensor isomorphism naturally lends itself to algebraic and semi-algebraic proof systems such as the polynomial calculus (PC) and sum-of-squares (SoS). We show a linear degree lower bound on PC degree or SoS degree for tensor isomorphism and a non-trivial upper bound for testing isomorphism of tensors of bounded rank. Along the way, we also show that PC cannot perform basic linear algebra in sublinear degree, such as comparing the rank of two matrices. We introduce a strictly stronger proof system, called PC + Inv, which enables linear algebra to be done in low degree. We conjecture that even PC + Inv cannot solve TI in polynomial time either, and highlight many other open questions about proof complexity approaches to TI.
In unitary property testing a quantum algorithm, also known as a tester, is given query access to a black-box unitary and has to decide whether it satisfies some property. We propose a new technique for proving lower bounds on the quantum query complexity of unitary property testing and related problems, which utilises its connection to unitary channel discrimination. The main advantage of this technique is that all obtained lower bounds hold for any C -tester with C⊆QMA(2)/qpoly , showing that even having access to both (unentangled) quantum proofs and advice does not help for many unitary property testing problems. We apply our technique to prove lower bounds for problems like quantum phase estimation, the entanglement entropy problem, quantum Gibbs sampling and more, removing all logarithmic factors in the lower bounds obtained by the sample-to-query lifting theorem of Wang and Zhang (2023). As a direct corollary, we show that there exist quantum oracles relative to which QMA(2)⊅SBQP and QMA/qpoly⊅SBQP . The former shows that, at least in a black-box way, having unentangled quantum proofs does not help in solving problems that require high precision.
Query complexity studies the amount of information about an input that is needed to solve a computational problem. This thesis investigates query complexity in several settings, with applications to cryptography and property testing, as well as connections to communication complexity and other computational models. In property testing, we study tolerant junta testing and establish the first superpolynomial quantum advantage for this problem: within a certain parameter regime, a quantum algorithm uses polynomially many queries, whereas every classical randomised algorithm requires quasipolynomially many queries. In cryptography, we study the average-case complexity of search problems. We show that verifiable delay functions do not exist in the random oracle model, and strengthen known barriers to constructing average-case hard TFNP problems from one-way functions. Finally, we study lower bounds and their behaviour across computational models. We prove new direct sum results for randomised parity decision trees. We also establish a new separation between query complexity measures of total Boolean functions and, through query-to-communication lifting, derive new communication lower bounds and lower bounds for unambiguous finite automata.
Abstract. The polynomial method by Beals, Buhrman, Cleve, Mosca, and de Wolf (FOCS 1998; [ J. ACM, 48 (2001), pp. 778–797]) and the adversary method by Ambainis (STOC 2000; [ J. Comput. System Sci., 64 (2002), pp. 750–767]) and the compressed oracle method by Zhandry [ Proceedings of the 39 th CRYPTO, 2019, pp. 239–268] have been shown to be powerful in proving quantum query lower bounds for a wide variety of problems. In this paper, we propose a new method for proving quantum query lower bounds by a quantum sample-to-query lifting theorem, which is from an information theory perspective. Using this method, we obtain the following new results: (1) A quadratic relation between quantum sample and query complexities regarding quantum property testing, which is optimal and saturated by quantum state discrimination. Here, the sample complexity is measured given sample access to the quantum state to be tested, while the query complexity is measured given query access to an oracle that block-encodes the quantum state. (2) A matching lower bound [Formula: see text] for quantum Gibbs sampling at inverse temperature [Formula: see text] ([Formula: see text] suppresses logarithmic factors), showing that the quantum Gibbs sampler by Gilyén, Su, Low, and Wiebe [ Proceedings of the 51 st STOC, 2019, pp. 193–204] is optimal. (3) A new lower bound [Formula: see text] for the entanglement entropy problem with gap [Formula: see text], which was recently studied by She and Yuen [ Proceedings of the 14 th ITCS, 2023, pp. 96:1–96:17]. (4) A series of quantum query lower bounds for matrix spectrum testing, based on the sample lower bounds for quantum state spectrum testing by O’Donnell and Wright (STOC 2015; [ Comm. Math. Phys., 387 (2021), pp. 1–95]). In addition, we provide unified proofs for some known lower bounds that have been proven previously via different techniques, including those for phase/amplitude estimation and Hamiltonian simulation.
Quantum sample-to-query lifting, a relation between quantum sample complexity and quantum query complexity presented in Wang and Zhang (SIAM J. Comput. 2025), was significantly strengthened by Tang, Wright, and Zhandry (2025) to the case of state-preparation oracles. In this paper, we compile a list of quantum lower and upper bounds for property testing that are obtained by quantum sample-to-query lifting. The problems of interest include testing properties of probability distributions and quantum states, such as entropy and closeness. This collection contains new results, as well as new proofs of known bounds. In total, we present 49 complexity bounds, where 41 are new and 18 are (near-)optimal.
In this work, we study bipartiteness and expansion testing, two canonical problems in graph property testing in the bounded-degree model through the lens of quantum query complexity. In the classical setting, it is known that Θ(N) queries are necessary and sufficient for both these testing problems (Goldreich and Ron, 1999, 2000 & 2002), where N denotes the number of vertices of the input graph. Due to their significance, (Ambainis, Childs, and Liu, 2011) initiated the study of these problems in the quantum setting and designed quantum algorithms for bipartiteness and expansion testing that perform O(N1/3) queries, showing a polynomial speedup. They also proved that Ω(N1/4) queries are necessary for expansion testing, but the possibility of an exponential quantum advantage for bipartiteness testing remained open. Despite significant effort, there has been no improvement in these results in the last decade and a half. In this work, we prove essentially tight Ω(N1/3) quantum query lower bounds for both bipartiteness and expansion testing, thereby completely characterizing the quantum query complexity of these problems up to polylogarithmic factors. While our proofs use the polynomial method similarly to Ambainis, Childs, and Liu, we use intermediate problems that we relate to the main problems via reductions, and perform a more precise analysis of the resulting polynomials, leading to the near-optimal lower bounds.