78 Search Results for "Buhrman, Harry"

Document
DOI: 10.4230/LIPIcs.STACS.2026.66
Computational Hardness of Estimating Quantum Entropies via Binary Entropy Bounds

Authors: Yupan Liu

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We investigate the computational hardness of estimating the quantum α-Rényi entropy S^𝚁_α(ρ) = (ln Tr(ρ^α))/(1-α) and the quantum q-Tsallis entropy S^𝚃_q(ρ) = (1-Tr(ρ^q))/(q-1), both converging to the von Neumann entropy as the order approaches 1. The promise problems Quantum α-Rényi Entropy Approximation (RényiQEA_α) and Quantum q-Tsallis Entropy Approximation (TsallisQEA_q) ask whether S^𝚁_α(ρ) or S^𝚃_q(ρ), respectively, is at least τ_Y or at most τ_N, where τ_Y - τ_N is typically a positive constant. Previous hardness results cover only the von Neumann entropy (order 1) and some cases of the quantum q-Tsallis entropy, while existing approaches do not readily extend to other orders. We establish that for all positive real orders, the rank-2 variants Rank2RényiQEA_α and Rank2TsallisQEA_q are BQP-hard. Combined with prior (rank-dependent) quantum query algorithms in Wang, Guan, Liu, Zhang, and Ying (TIT 2024), Wang, Zhang, and Li (TIT 2024), and Liu and Wang (SODA 2025), our results imply: - For all real order α > 0 and 0 < q ≤ 1, LowRankRényiQEA_α and LowRankTsallisQEA_q are BQP-complete, where both are restricted versions of RényiQEA_α and TsallisQEA_q with ρ of polynomial rank. - For all real order q > 1, TsallisQEA_q is BQP-complete. Our hardness results stem from reductions based on new inequalities relating the α-Rényi or q-Tsallis binary entropies of different orders, where the reductions differ substantially from previous approaches, and the inequalities are also of independent interest.
Cite as

Yupan Liu. Computational Hardness of Estimating Quantum Entropies via Binary Entropy Bounds. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 66:1-66:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{liu:LIPIcs.STACS.2026.66,
  author =	{Liu, Yupan},
  title =	{{Computational Hardness of Estimating Quantum Entropies via Binary Entropy Bounds}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{66:1--66:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.66},
  URN =		{urn:nbn:de:0030-drops-255550},
  doi =		{10.4230/LIPIcs.STACS.2026.66},
  annote =	{Keywords: computational hardness, quantum state testing, quantum R\'{e}nyi entropy, quantum Tsallis entropy, von Neumann entropy}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.43
Efficient Catalytic Graph Algorithms

Authors: James Cook and Edward Pyne

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We give fast, simple, and implementable catalytic logspace algorithms for two fundamental graph problems. First, a randomized catalytic algorithm for s → t connectivity running in Õ(nm) time, and a deterministic catalytic algorithm for the same running in Õ(n³ m) time. The former algorithm is the first algorithmic use of randomization in CL. The algorithm uses one register per vertex and repeatedly "pushes" values along the edges in the graph. Second, a deterministic catalytic algorithm for simulating random walks which in Õ(m T² / ε) time estimates the probability a T-step random walk ends at a given vertex within ε additive error. The algorithm uses one register for each vertex and increments it at each visit to ensure repeated visits follow different outgoing edges. Prior catalytic algorithms for both problems did not have explicit runtime bounds beyond being polynomial in n.
Cite as

James Cook and Edward Pyne. Efficient Catalytic Graph Algorithms. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 43:1-43:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cook_et_al:LIPIcs.ITCS.2026.43,
  author =	{Cook, James and Pyne, Edward},
  title =	{{Efficient Catalytic Graph Algorithms}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{43:1--43:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.43},
  URN =		{urn:nbn:de:0030-drops-253305},
  doi =		{10.4230/LIPIcs.ITCS.2026.43},
  annote =	{Keywords: catalytic computing, graph algorithms, catalytic logspace}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.10
On the Complexity of Unique Quantum Witnesses and Quantum Approximate Counting

Authors: Anurag Anshu, Jonas Haferkamp, Yeongwoo Hwang, and Quynh T. Nguyen

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We study the long-standing open question on the power of unique witnesses in quantum protocols, which asks if UniqueQMA, a variant of QMA whose accepting witness space is 1-dimensional, contains QMA under quantum reductions. This work rules out any black-box reduction from QMA to UniqueQMA by showing a quantum oracle separation between BQP^UniqueQMA and QMA. This provides a contrast to the classical case, where the Valiant-Vazirani theorem shows a black-box randomized reduction from UniqueNP to NP, and suggests the need for studying the structure of the ground space of local Hamiltonians in distilling a potential unique witness. Via similar techniques, we show, relative to a quantum oracle, that QMA^QMA cannot decide quantum approximate counting, ruling out a quantum analogue of Stockmeyer’s algorithm in the black-box setting. Our results employ a subspace reflection oracle, previously considered in [Scott Aaronson and Greg Kuperberg, 2007; Scott Aaronson et al., 2020; She and Yuen, 2023], but we introduce new tools which allow us to exploit the unique witness constraint. We also show a strong "polarization" behavior of QMA circuits, which could be of independent interest in studying quantum polynomial hierarchies. We then ask a natural question; what structural properties of the local Hamiltonian problem can we exploit? We introduce a physically motivated candidate by showing that the ground energy of local Hamiltonians that satisfy a computational variant of the eigenstate thermalization hypothesis (ETH) can be estimated through a UniqueQMA protocol. Our protocol can be viewed as a quantum expander test in a low energy subspace of the Hamiltonian and verifies a unique entangled state across two copies of the subspace. This allows us to conclude that if UniqueQMA is not equivalent to QMA, then QMA-hard Hamiltonians must violate ETH under adversarial perturbations (more accurately, further assuming the quantum PCP conjecture if ETH only applies to extensive energy subspaces). Under the same assumption, this also serves as evidence that chaotic local Hamiltonians, such as the SYK model may be computationally simpler than general local Hamiltonians.
Cite as

Anurag Anshu, Jonas Haferkamp, Yeongwoo Hwang, and Quynh T. Nguyen. On the Complexity of Unique Quantum Witnesses and Quantum Approximate Counting. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{anshu_et_al:LIPIcs.ITCS.2026.10,
  author =	{Anshu, Anurag and Haferkamp, Jonas and Hwang, Yeongwoo and Nguyen, Quynh T.},
  title =	{{On the Complexity of Unique Quantum Witnesses and Quantum Approximate Counting}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.10},
  URN =		{urn:nbn:de:0030-drops-252978},
  doi =		{10.4230/LIPIcs.ITCS.2026.10},
  annote =	{Keywords: Quantum complexity, approximate counting, Valiant-Vazirani, eigenstate thermalization hypothesis}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.60
Total Search Problems in ZPP

Authors: Noah Fleming, Stefan Grosser, Siddhartha Jain, Jiawei Li, Hanlin Ren, Morgan Shirley, and Weiqiang Yuan

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We initiate a systematic study of TFZPP, the class of total NP search problems solvable by polynomial time randomized algorithms. TFZPP contains a variety of important search problems such as Bertrand-Chebyshev (finding a prime between N and 2N), refuter problems for many circuit lower bounds, and Lossy-Code. The Lossy-Code problem has found prominence due to its fundamental connections to derandomization, catalytic computing, and the metamathematics of complexity theory, among other areas. While TFZPP collapses to FP under standard derandomization assumptions in the white-box setting, we are able to separate TFZPP from the major TFNP subclasses in the black-box setting. In fact, we are able to separate it from every uniform TFNP class assuming that NP is not in quasi-polynomial time. To do so, we extend the connection between proof complexity and black-box TFNP to randomized proof systems and randomized reductions. Next, we turn to developing a taxonomy of TFZPP problems. We highlight a problem called Nephew, originating from an infinity axiom in set theory. We show that Nephew is in PWPP∩ TFZPP and conjecture that it is not reducible to Lossy-Code. Intriguingly, except for some artificial examples, most other black-box TFZPP problems that we are aware of reduce to Lossy-Code: - We define a problem called Empty-Child capturing finding a leaf in a rooted (binary) tree, and show that this problem is equivalent to Lossy-Code. We also show that a variant of Empty-Child with "heights" is complete for the intersection of SOPL and Lossy-Code. - We strengthen Lossy-Code with several combinatorial inequalities such as the AM-GM inequality. Somewhat surprisingly, we show the resulting new problems are still reducible to Lossy-Code. A technical highlight of this result is that they are proved by formalizations in bounded arithmetic, specifically in Jeřábek’s theory APC₁ (JSL 2007). - Finally, we show that the Dense-Linear-Ordering problem reduces to Lossy-Code.
Cite as

Noah Fleming, Stefan Grosser, Siddhartha Jain, Jiawei Li, Hanlin Ren, Morgan Shirley, and Weiqiang Yuan. Total Search Problems in ZPP. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 60:1-60:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fleming_et_al:LIPIcs.ITCS.2026.60,
  author =	{Fleming, Noah and Grosser, Stefan and Jain, Siddhartha and Li, Jiawei and Ren, Hanlin and Shirley, Morgan and Yuan, Weiqiang},
  title =	{{Total Search Problems in ZPP}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{60:1--60:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.60},
  URN =		{urn:nbn:de:0030-drops-253473},
  doi =		{10.4230/LIPIcs.ITCS.2026.60},
  annote =	{Keywords: TFNP, lossy code, randomized proof systems, query complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.61
Random Unitaries in Constant (Quantum) Time

Authors: Ben Foxman, Natalie Parham, Francisca Vasconcelos, and Henry Yuen

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Random unitaries are a central object of study in quantum information, with applications to quantum computation, quantum many-body physics, and quantum cryptography. Recent work has constructed unitary designs and pseudorandom unitaries (PRUs) using Θ(log log n)-depth unitary circuits with two-qubit gates. In this work, we show that unitary designs and PRUs can be efficiently constructed in several well-studied models of constant-time quantum computation (i.e., the time complexity on the quantum computer is independent of the system size). These models are constant-depth circuits augmented with certain nonlocal operations, such as (a) many-qubit TOFFOLI gates, (b) many-qubit FANOUT gates, or (c) mid-circuit measurements with classical feedforward control. Recent advances in quantum computing hardware suggest experimental feasibility of these models in the near future. Our results demonstrate that unitary designs and PRUs can be constructed in much weaker circuit models than previously thought. Furthermore, our construction of PRUs in constant-depth with many-qubit TOFFOLI gates shows that, under cryptographic assumptions, there is no polynomial-time learning algorithm for the circuit class QAC⁰. Finally, our results suggest a new approach towards proving that PARITY is not computable in QAC⁰, a long-standing question in quantum complexity theory.
Cite as

Ben Foxman, Natalie Parham, Francisca Vasconcelos, and Henry Yuen. Random Unitaries in Constant (Quantum) Time. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 61:1-61:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{foxman_et_al:LIPIcs.ITCS.2026.61,
  author =	{Foxman, Ben and Parham, Natalie and Vasconcelos, Francisca and Yuen, Henry},
  title =	{{Random Unitaries in Constant (Quantum) Time}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{61:1--61:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.61},
  URN =		{urn:nbn:de:0030-drops-253481},
  doi =		{10.4230/LIPIcs.ITCS.2026.61},
  annote =	{Keywords: Quantum Information, Pseudorandomness, Circuit Complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.2
Oracle Separations for the Quantum-Classical Polynomial Hierarchy

Authors: Avantika Agarwal and Shalev Ben{-}David

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We study 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. Our lemma says that for any d, if we apply a random restriction to a function f with quantum query complexity Q(f) ≤ n^{1/3}, the restricted function becomes exponentially close (in terms of d) to a depth-d decision tree. Our switching lemma works even in a "worst-case" sense, in that only the indices to be restricted are random; the values they are restricted to are chosen adversarially. Moreover, the switching lemma also works for polynomial degree in place of quantum query complexity.
Cite as

Avantika Agarwal and Shalev Ben-David. Oracle Separations for the Quantum-Classical Polynomial Hierarchy. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 2:1-2:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.ITCS.2026.2,
  author =	{Agarwal, Avantika and Ben\{-\}David, Shalev},
  title =	{{Oracle Separations for the Quantum-Classical Polynomial Hierarchy}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{2:1--2:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.2},
  URN =		{urn:nbn:de:0030-drops-252893},
  doi =		{10.4230/LIPIcs.ITCS.2026.2},
  annote =	{Keywords: Switching Lemma, Polynomial Hierarchy, Approximate Degree, Random Oracles, Query Complexity, Quantum Computing}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.3
Linear Matroid Intersection Is in Catalytic Logspace

Authors: Aryan Agarwala, Yaroslav Alekseev, and Antoine Vinciguerra

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Linear matroid intersection is an important problem in combinatorial optimization. Given two linear matroids over the same ground set, the linear matroid intersection problem asks you to find a common independent set of maximum size. The deep interest in linear matroid intersection is due to the fact that it generalises many classical problems in theoretical computer science, such as bipartite matching, edge disjoint spanning trees, rainbow spanning tree, and many more. We study this problem in the model of catalytic computation: space-bounded machines are granted access to catalytic space, which is additional working memory that is full with arbitrary data that must be preserved at the end of its computation. Although linear matroid intersection has had a polynomial time algorithm for over 50 years, it remains an important open problem to show that linear matroid intersection belongs to any well studied subclass of {P}. We address this problem for the class catalytic logspace (CL) with a polynomial time bound (CLP). Recently, Agarwala and Mertz (2025) showed that bipartite maximum matching can be computed in the class CLP ⊆ {P}. This was the first subclass of {P} shown to contain bipartite matching, and additionally the first problem outside TC¹ shown to be contained in CL. We significantly improve the result of Agarwala and Mertz by showing that linear matroid intersection can be computed in CLP.
Cite as

Aryan Agarwala, Yaroslav Alekseev, and Antoine Vinciguerra. Linear Matroid Intersection Is in Catalytic Logspace. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 3:1-3:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{agarwala_et_al:LIPIcs.ITCS.2026.3,
  author =	{Agarwala, Aryan and Alekseev, Yaroslav and Vinciguerra, Antoine},
  title =	{{Linear Matroid Intersection Is in Catalytic Logspace}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{3:1--3:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.3},
  URN =		{urn:nbn:de:0030-drops-252908},
  doi =		{10.4230/LIPIcs.ITCS.2026.3},
  annote =	{Keywords: Catalytic Computing, Computational Complexity, Matroid Theory, Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.72
Forrelation Is Extremally Hard

Authors: Uma Girish and Rocco Servedio

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
The Forrelation problem is a central problem that demonstrates an exponential separation between quantum and classical capabilities. In this problem, given query access to n-bit Boolean functions f and g, the goal is to estimate the Forrelation function forr(f,g), which measures the correlation between g and the Fourier transform of f. In this work we provide a new linear algebraic perspective on the Forrelation problem, as opposed to prior analytic approaches. We establish a connection between the Forrelation problem and bent Boolean functions and through this connection, analyze an extremal version of the Forrelation problem where the goal is to distinguish between extremal instances of Forrelation, namely (f,g) with forr(f,g) = 1 and forr(f,g) = -1. We show that this problem can be solved with one quantum query and success probability one, yet requires Ω̃(2^{n/4}) classical randomized queries, even for algorithms with a one-third failure probability, highlighting the remarkable power of one exact quantum query. We also study a restricted variant of this problem where the inputs f,g are computable by small classical circuits and show classical hardness under cryptographic assumptions.
Cite as

Uma Girish and Rocco Servedio. Forrelation Is Extremally Hard. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 72:1-72:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{girish_et_al:LIPIcs.ITCS.2026.72,
  author =	{Girish, Uma and Servedio, Rocco},
  title =	{{Forrelation Is Extremally Hard}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{72:1--72:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.72},
  URN =		{urn:nbn:de:0030-drops-253594},
  doi =		{10.4230/LIPIcs.ITCS.2026.72},
  annote =	{Keywords: Forrelation, exact quantum, query complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.34
Testing Classical Properties from Quantum Data

Authors: Matthias C. Caro, Preksha Naik, and Joseph Slote

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Many properties of Boolean functions can be tested far more efficiently than the function itself can be learned. However, this dramatic advantage often disappears when testers are limited to random samples of f instead of adaptively chosen queries to f. In this work we investigate the quantum version of this restriction: quantum algorithms that test properties of a Boolean function f solely from copies of either the function state |f⟩∝ ∑_x|x,f(x)⟩ or the phase state |(-1)^f⟩∝ ∑_x (-1)^{f(x)}|x⟩. Quantum advantage in testing from data. For monotonicity, symmetry, and triangle-freeness, we show passive quantum testers are unboundedly or super-polynomially better than their classical passive testing counterparts. They are competitive with classic query-based testers in each case. Inadequacy of Fourier sampling. Our new testers use techniques beyond quantum Fourier sampling, and it turns out this is necessary: we show a certain class of bent functions can be tested from 𝒪(1) function states but has a sample complexity lower bound of 2^{Ω(n)} for any tester relying exclusively on Fourier and classical samples. Classical queries vs. quantum data. Our passive quantum testers are competitive with classical query-based testers, but this isn't universal: we exhibit a testing problem that can be solved from 𝒪(1) classical queries but requires Ω(2^{n/2}) function state copies. The Forrelation problem provides a separation of the same magnitude in the opposite direction, so we conclude that quantum data and classical queries are "maximally incomparable" resources for testing. Towards lower bounds. We also begin the study of lower bounds for testing from quantum data. For quantum monotonicity testing, we prove that the ensembles of [Goldreich et al., 2000; Black, 2024], which give exponential lower bounds for classical sample-based testing, do not yield any nontrivial lower bounds for testing from quantum data. New insights specific to quantum data will be required for proving copy complexity lower bounds for testing in this model.
Cite as

Matthias C. Caro, Preksha Naik, and Joseph Slote. Testing Classical Properties from Quantum Data. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 34:1-34:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{caro_et_al:LIPIcs.ITCS.2026.34,
  author =	{Caro, Matthias C. and Naik, Preksha and Slote, Joseph},
  title =	{{Testing Classical Properties from Quantum Data}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{34:1--34:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.34},
  URN =		{urn:nbn:de:0030-drops-253213},
  doi =		{10.4230/LIPIcs.ITCS.2026.34},
  annote =	{Keywords: Quantum Property Testing, Quantum Data, Boolean Functions}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.37
New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String

Authors: Lijie Chen, Yang Hu, and Hanlin Ren

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
The algebrization barrier, proposed by Aaronson and Wigderson (STOC '08, ToCT '09), captures the limitations of many complexity-theoretic techniques based on arithmetization. Notably, several circuit lower bounds that overcome the relativization barrier (Buhrman-Fortnow-Thierauf, CCC '98; Vinodchandran, TCS '05; Santhanam, STOC '07, SICOMP '09) remain subject to the algebrization barrier. In this work, we establish several new algebrization barriers to circuit lower bounds by studying the communication complexity of the following problem, called XOR-Missing-String: For m < 2^{n/2}, Alice gets a list of m strings x₁, … , x_m ∈ {0, 1}ⁿ, Bob gets a list of m strings y₁, … , y_m ∈ {0, 1}ⁿ, and the goal is to output a string s ∈ {0, 1}ⁿ that is not equal to x_i⊕ y_j for any i, j ∈ [m]. 1) We construct an oracle A₁ and its multilinear extension A₁̃ such that PostBPE^{A₁̃} has linear-size A₁-oracle circuits on infinitely many input lengths. That is, proving PostBPE ̸ ⊆ i.o.- SIZE[O(n)] requires non-algebrizing techniques. This barrier follows from a PostBPP communication lower bound for XOR-Missing-String. This is in contrast to the well-known algebrizing lower bound MA_E (⊆ PostBPE) ̸ ⊆ P/_poly. 2) We construct an oracle A₂ and its multilinear extension A₂̃ such that BPE^{A₂̃} has linear-size A₂-oracle circuits on all input lengths. Previously, a similar barrier was demonstrated by Aaronson and Wigderson, but in their result, A₂̃ is only a multiquadratic extension of A₂. Our results show that communication complexity is more useful than previously thought for proving algebrization barriers, as Aaronson and Wigderson wrote that communication-based barriers were "more contrived". This serves as an example of how XOR-Missing-String forms new connections between communication lower bounds and algebrization barriers. 3) Finally, we study algebrization barriers to circuit lower bounds for MA_E. Buhrman, Fortnow, and Thierauf proved a sub-half-exponential circuit lower bound for MA_E via algebrizing techniques. Toward understanding whether the half-exponential bound can be improved, we define a natural subclass of MA_E that includes their hard MA_E language, and prove the following result: For every super-half-exponential function h(n), we construct an oracle A₃ and its multilinear extension A₃̃ such that this natural subclass of MA_E^{A₃̃} has h(n)-size A₃-oracle circuits on all input lengths. This suggests that half-exponential might be the correct barrier for MA_E circuit lower bounds w.r.t. algebrizing techniques.
Cite as

Lijie Chen, Yang Hu, and Hanlin Ren. New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ITCS.2026.37,
  author =	{Chen, Lijie and Hu, Yang and Ren, Hanlin},
  title =	{{New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{37:1--37:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.37},
  URN =		{urn:nbn:de:0030-drops-253246},
  doi =		{10.4230/LIPIcs.ITCS.2026.37},
  annote =	{Keywords: circuit lower bound, algebrization barrier, missing string, communication complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.35
Symmetric Quantum Computation

Authors: Davi Castro-Silva, Tom Gur, and Sergii Strelchuk

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We introduce a systematic study of symmetric quantum circuits, a new restricted model of quantum computation that preserves the symmetries of the problems it solves. This model is well-adapted for studying the role of symmetry in quantum speedups, extending a central notion of symmetric computation studied in the classical setting. Our results establish that symmetric quantum circuits are fundamentally more powerful than their classical counterparts. First, we give efficient symmetric circuits for key quantum techniques such as amplitude amplification, phase estimation and linear combination of unitaries. In addition, we show how the task of symmetric state preparation can be performed efficiently in several natural cases. Finally, we demonstrate an exponential separation in the symmetric setting for the problem XOR-SAT, which requires exponential-size symmetric classical circuits but can be solved by polynomial-size symmetric quantum circuits.
Cite as

Davi Castro-Silva, Tom Gur, and Sergii Strelchuk. Symmetric Quantum Computation. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 35:1-35:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{castrosilva_et_al:LIPIcs.ITCS.2026.35,
  author =	{Castro-Silva, Davi and Gur, Tom and Strelchuk, Sergii},
  title =	{{Symmetric Quantum Computation}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{35:1--35:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.35},
  URN =		{urn:nbn:de:0030-drops-253223},
  doi =		{10.4230/LIPIcs.ITCS.2026.35},
  annote =	{Keywords: Quantum computing, complexity theory, symmetries}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.88
Lower Bounds and Separations for Torus Polynomials

Authors: Vaibhav Krishan and Sundar Vishwanathan

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
The class ACC⁰ consists of Boolean functions that can be computed by constant-depth circuits of polynomial size with AND, NOT and MOD_m gates, where m is a natural number. At the frontier of our understanding lies a widely believed conjecture asserting that MAJORITY does not belong to ACC⁰. A few years ago, Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019) introduced torus polynomial approximations as an approach towards this conjecture. Torus polynomials approximate Boolean functions when the fractional part of their value on Boolean points is close to half the value of the function. They reduced the conjecture that MAJORITY ∉ ACC⁰ to a conjecture concerning the non-existence of low degree torus polynomials that approximate MAJORITY. We reduce the non-existence problem further, to a statement about finding feasible solutions for an infinite family of linear programs. The main advantage of this statement is that it allows for incremental progress, which means finding feasible solutions for successively larger collections of these programs. As an immediate first step, we find feasible solutions for a large class of these linear programs, leaving only a finite set for further consideration. Our method is inspired by the method of dual polynomials, which is used to study the approximate degree of Boolean functions. Using our method, we also propose a way to progress further. We prove several additional key results with the same method, which include: - A lower bound on the degree of symmetric torus polynomials that approximate the AND function. As a consequence, we get a separation that symmetric torus polynomials are weaker than their asymmetric counterparts. - An error-degree trade-off for symmetric torus polynomials approximating the MAJORITY function, strengthening the corresponding result of Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019). - The first lower bounds against torus polynomials approximating AND, showcasing the power of the machinery we develop. This lower bound nearly matches the corresponding upper bound. Hence, we get an almost complete characterization of the torus polynomial approximation degree of AND. - Lower bounds against asymmetric torus polynomials approximating MAJORITY, or AND, in the very low error regime. This partially answers a question posed in Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019) about error-reduction for torus polynomials.
Cite as

Vaibhav Krishan and Sundar Vishwanathan. Lower Bounds and Separations for Torus Polynomials. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 88:1-88:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{krishan_et_al:LIPIcs.ITCS.2026.88,
  author =	{Krishan, Vaibhav and Vishwanathan, Sundar},
  title =	{{Lower Bounds and Separations for Torus Polynomials}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{88:1--88:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.88},
  URN =		{urn:nbn:de:0030-drops-253751},
  doi =		{10.4230/LIPIcs.ITCS.2026.88},
  annote =	{Keywords: Circuit complexity, ACC, lower bounds, polynomials}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2025.7
Mobile Byzantine Agreement in a Trusted World

Authors: Bo Pan and Maria Potop-Butucaru

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
In this paper, we address the Byzantine Agreement problem in synchronous systems where Byzantine agents can move from process to process, corrupting their host. We focus on two representative models: Garay’s and Buhrman’s models. In Garay’s model, when a process has been left by the Byzantine agent, it enters a cured state, is aware of its condition, and can remain silent for a round to prevent the dissemination of incorrect information. In Buhrman’s model, a Byzantine agent moves together with the message. It has been shown that solving Byzantine Agreement requires at least 4t + 1 processes in Garay’s model, and at least 3t + 1 in Buhrman’s model. In this paper, we aim to increase the tolerance to mobile Byzantine agents by integrating a trusted counter abstraction into both models. This abstraction prevents nodes from equivocating. In the new models, we prove that at least 3t+1, respectively 2t+1 processors are needed to tolerate t mobile Byzantine agents. Furthermore, we propose novel Mobile Byzantine Agreement algorithms that match these new lower bounds for both Garay’s and Buhrman’s models, achieving agreement in 𝒪(n) synchronous rounds.
Cite as

Bo Pan and Maria Potop-Butucaru. Mobile Byzantine Agreement in a Trusted World. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pan_et_al:LIPIcs.OPODIS.2025.7,
  author =	{Pan, Bo and Potop-Butucaru, Maria},
  title =	{{Mobile Byzantine Agreement in a Trusted World}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{7:1--7:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.7},
  URN =		{urn:nbn:de:0030-drops-251809},
  doi =		{10.4230/LIPIcs.OPODIS.2025.7},
  annote =	{Keywords: Byzantine Agreement, Mobile Faults, Trusted Abstractions}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.37
Communication Complexity of Equality and Error-Correcting Codes

Authors: Dale Jacobs, John Jeang, Vladimir Podolskii, Morgan Prior, and Ilya Volkovich

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
We study the public-coin randomized communication complexity of the equality function. The communication complexity of this function is known to be low when the error probability is constant and the players have access to many random bits. The complexity grows, however, if the allowed error probability and the amount of randomness are restricted. We show that public-coin randomized protocols for equality and error-correcting codes are essentially the same object. That is, given a protocol for equality, we can construct a code, and vice versa. We substantially extend the protocol-implies-code direction: any protocol computing a function with a large fooling set can be converted into an error-correcting code. As a corollary, we show that among functions with a fooling set of size s, equality on log s bits has the least randomized communication complexity, regardless of the restrictions on the error probability and the amount of randomness. Finally, we use the connection to error-correcting codes to analyze the randomized communication complexity of equality for varying restrictions on the error probability and the amount of randomness. In most cases, we provide tight bounds. We pinpoint the setting in which tight bounds are still unknown.
Cite as

Dale Jacobs, John Jeang, Vladimir Podolskii, Morgan Prior, and Ilya Volkovich. Communication Complexity of Equality and Error-Correcting Codes. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 37:1-37:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jacobs_et_al:LIPIcs.FSTTCS.2025.37,
  author =	{Jacobs, Dale and Jeang, John and Podolskii, Vladimir and Prior, Morgan and Volkovich, Ilya},
  title =	{{Communication Complexity of Equality and Error-Correcting Codes}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{37:1--37:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.37},
  URN =		{urn:nbn:de:0030-drops-251175},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.37},
  annote =	{Keywords: communication complexity, randomized communication complexity, error-correcting codes}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.4
Optimal Quantum Algorithm for Estimating Fidelity to a Pure State

Authors: Wang Fang and Qisheng Wang

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We present an optimal quantum algorithm for fidelity estimation between two quantum states when one of them is pure. In particular, the (square root) fidelity of a mixed state to a pure state can be estimated to within additive error ε by using Θ(1/ε) queries to their state-preparation circuits, achieving a quadratic speedup over the folklore O(1/ε²). Our approach is technically simple, and can moreover estimate the quantity √{tr(ρσ²)} that is not common in the literature. To the best of our knowledge, this is the first query-optimal approach to fidelity estimation involving mixed states.
Cite as

Wang Fang and Qisheng Wang. Optimal Quantum Algorithm for Estimating Fidelity to a Pure State. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fang_et_al:LIPIcs.ESA.2025.4,
  author =	{Fang, Wang and Wang, Qisheng},
  title =	{{Optimal Quantum Algorithm for Estimating Fidelity to a Pure State}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{4:1--4:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.4},
  URN =		{urn:nbn:de:0030-drops-244727},
  doi =		{10.4230/LIPIcs.ESA.2025.4},
  annote =	{Keywords: Quantum computing, fidelity estimation, quantum algorithms, quantum query complexity}
}
  • Refine by Type
  • 78 Document/PDF
  • 48 Document/HTML

  • Refine by Publication Year
  • 13 2026
  • 35 2025
  • 3 2024
  • 1 2023
  • 2 2022
  • Show More...

  • Refine by Author
  • 19 Buhrman, Harry
  • 9 Speelman, Florian
  • 5 Fortnow, Lance
  • 4 Patro, Subhasree
  • 4 Thierauf, Thomas
  • Show More...

  • Refine by Series/Journal
  • 62 LIPIcs
  • 1 DagSemRep
  • 15 DagSemProc

  • Refine by Classification
  • 16 Theory of computation → Quantum complexity theory
  • 11 Theory of computation → Complexity classes
  • 8 Theory of computation → Quantum query complexity
  • 7 Theory of computation → Circuit complexity
  • 6 Theory of computation → Quantum computation theory
  • Show More...

  • Refine by Keyword
  • 7 quantum computing
  • 5 communication complexity
  • 5 lower bounds
  • 4 complexity theory
  • 4 quantum algorithms
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact