DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2026.11

Classical and Quantum Polynomial Freiman-Ruzsa Algorithms

Authors: Srinivasan Arunachalam, Davi Castro-Silva, Arkopal Dutt, and Tom Gur

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

Abstract

We prove algorithmic versions of the polynomial Freiman-Ruzsa theorem of Gowers, Green, Manners, and Tao (Annals of Mathematics, 2025) in additive combinatorics. In particular, we give classical and quantum polynomial-time algorithms that, for A ⊆ 𝔽₂ⁿ with doubling constant K, learn an explicit description of a subspace V ⊆ 𝔽₂ⁿ of size |V| ≤ |A| such that A can be covered by K^C translates of V, for a universal constant C > 1.

Cite as

Srinivasan Arunachalam, Davi Castro-Silva, Arkopal Dutt, and Tom Gur. Classical and Quantum Polynomial Freiman-Ruzsa Algorithms. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 11:1-11:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.ITCS.2026.11,
  author =	{Arunachalam, Srinivasan and Castro-Silva, Davi and Dutt, Arkopal and Gur, Tom},
  title =	{{Classical and Quantum Polynomial Freiman-Ruzsa Algorithms}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{11:1--11:8},
  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.11},
  URN =		{urn:nbn:de:0030-drops-252987},
  doi =		{10.4230/LIPIcs.ITCS.2026.11},
  annote =	{Keywords: Additive combinatorics, sublinear algorithms}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.56

The Hardness of Learning Quantum Circuits and Its Cryptographic Applications

Authors: Bill Fefferman, Soumik Ghosh, Makrand Sinha, and Henry Yuen

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

Abstract

We show that concrete hardness assumptions about learning or cloning the output state of a random quantum circuit can be used as the foundation for secure quantum cryptography. In particular, under these assumptions we construct secure one-way state generators (OWSGs), digital signature schemes, quantum bit commitments, and private key encryption schemes. We also discuss evidence for these hardness assumptions by analyzing the best-known quantum learning algorithms, as well as proving black-box lower bounds for cloning and learning given state preparation oracles. Our random circuit-based constructions provide concrete instantiations of quantum cryptographic primitives whose security do not depend on the existence of one-way functions. The use of random circuits in our constructions also opens the door to {NISQ-friendly quantum cryptography}. We discuss noise tolerant versions of our OWSG and digital signature constructions which can potentially be implementable on noisy quantum computers connected by a quantum network. On the other hand, they are still secure against {noiseless} quantum adversaries, raising the intriguing possibility of a useful implementation of an end-to-end cryptographic protocol on near-term quantum computers. Finally, our explorations suggest that the rich interconnections between learning theory and cryptography in classical theoretical computer science also extend to the quantum setting.

Cite as

Bill Fefferman, Soumik Ghosh, Makrand Sinha, and Henry Yuen. The Hardness of Learning Quantum Circuits and Its Cryptographic Applications. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 56:1-56:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fefferman_et_al:LIPIcs.ITCS.2026.56,
  author =	{Fefferman, Bill and Ghosh, Soumik and Sinha, Makrand and Yuen, Henry},
  title =	{{The Hardness of Learning Quantum Circuits and Its Cryptographic Applications}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{56:1--56:21},
  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.56},
  URN =		{urn:nbn:de:0030-drops-253431},
  doi =		{10.4230/LIPIcs.ITCS.2026.56},
  annote =	{Keywords: quantum learning, quantum circuits, cryptographic hardness, one-way state generators}
}

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.24

Unitary Complexity and the Uhlmann Transformation Problem

Authors: John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, Luowen Qian, and Henry Yuen

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

Abstract

State transformation problems such as compressing quantum information or breaking quantum commitments are fundamental quantum tasks. However, their computational difficulty cannot easily be characterized using traditional complexity theory, which focuses on tasks with classical inputs and outputs. To study the complexity of such state transformation tasks, we introduce a framework for unitary synthesis problems, including notions of reductions and unitary complexity classes. We use this framework to study the complexity of transforming one entangled state into another via local operations. We formalize this as the Uhlmann Transformation Problem, an algorithmic version of Uhlmann’s theorem. Then, we prove structural results relating the complexity of the Uhlmann Transformation Problem, polynomial space quantum computation, and zero knowledge protocols. The Uhlmann Transformation Problem allows us to characterize the complexity of a variety of tasks in quantum information processing, including decoding noisy quantum channels, breaking falsifiable quantum cryptographic assumptions, implementing optimal prover strategies in quantum interactive proofs, and decoding the Hawking radiation of black holes. Our framework for unitary complexity thus provides new avenues for studying the computational complexity of many natural quantum information processing tasks.

Cite as

John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, Luowen Qian, and Henry Yuen. Unitary Complexity and the Uhlmann Transformation Problem. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bostanci_et_al:LIPIcs.ITCS.2026.24,
  author =	{Bostanci, John and Efron, Yuval and Metger, Tony and Poremba, Alexander and Qian, Luowen and Yuen, Henry},
  title =	{{Unitary Complexity and the Uhlmann Transformation Problem}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{24:1--24:17},
  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.24},
  URN =		{urn:nbn:de:0030-drops-253111},
  doi =		{10.4230/LIPIcs.ITCS.2026.24},
  annote =	{Keywords: Uhlmann’s theorem, unitary complexity theory}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.70

Unconditional Pseudorandomness Against Shallow Quantum Circuits

Authors: Soumik Ghosh, Sathyawageeswar Subramanian, and Wei Zhan

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

Abstract

Quantum computational pseudorandomness has emerged as a fundamental notion that spans connections to complexity theory, cryptography and fundamental physics. However, all known constructions of efficient quantum-secure pseudorandom objects rely on complexity theoretic assumptions. In this work, we establish the first unconditionally secure efficient pseudorandom constructions against shallow-depth quantum circuit classes. We prove that: - Any quantum state 2-design yields unconditional pseudorandomness against both QNC⁰ circuits with arbitrarily many ancillae and AC⁰∘QNC⁰ circuits with nearly linear ancillae. - Random phased subspace states, where the phases are picked using a 4-wise independent function, are unconditionally pseudoentangled against the above circuit classes. - Any unitary 2-design yields unconditionally secure parallel-query pseudorandom unitaries against geometrically local QNC⁰ adversaries, even with limited AC⁰ postprocessing. Our results stand in stark contrast to the standard guarantee of the 2-design property, which only ensures that they cannot be distinguished from Haar random ensembles using two copies or queries. Our work demonstrates that quantum computational pseudorandomness can be achieved unconditionally for natural classes of restricted adversaries, opening new directions in quantum complexity theory.

Cite as

Soumik Ghosh, Sathyawageeswar Subramanian, and Wei Zhan. Unconditional Pseudorandomness Against Shallow Quantum Circuits. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 70:1-70:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ghosh_et_al:LIPIcs.ITCS.2026.70,
  author =	{Ghosh, Soumik and Subramanian, Sathyawageeswar and Zhan, Wei},
  title =	{{Unconditional Pseudorandomness Against Shallow Quantum Circuits}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{70:1--70: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.70},
  URN =		{urn:nbn:de:0030-drops-253578},
  doi =		{10.4230/LIPIcs.ITCS.2026.70},
  annote =	{Keywords: quantum pseudorandomness, shallow quantum circuits, pseudorandomness, t-designs}
}

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.108

The Learning Stabilizers with Noise Problem

Authors: Alexander Poremba, Yihui Quek, and Peter Shor

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

Abstract

Random classical codes have good error correcting properties, and yet they are notoriously hard to decode in practice. Despite many decades of extensive study, the fastest known algorithms still run in exponential time. The Learning Parity with Noise (LPN) problem, which can be seen as the task of decoding a random linear code in the presence of noise, has thus emerged as a prominent hardness assumption with numerous applications in both cryptography and learning theory. Is there a natural quantum analog of the LPN problem? In this work, we introduce the Learning Stabilizers with Noise (LSN) problem, the task of decoding a random stabilizer code in the presence of local depolarizing noise. We give both polynomial-time and exponential-time quantum algorithms for solving LSN in various depolarizing noise regimes, ranging from extremely low noise, to low constant noise rates, and even higher noise rates up to a threshold. Next, we provide concrete evidence that LSN is hard. First, we show that LSN includes LPN as a special case, which suggests that it is at least as hard as its classical counterpart. Second, we prove worst-case to average-case reductions for variants of LSN. We then ask: what is the computational complexity of solving LSN? Because the task features quantum inputs, its complexity cannot be characterized by traditional complexity classes. Instead, we show that the LSN problem lies in a recently introduced (distributional and oracle) unitary synthesis class. Finally, we identify several applications of our LSN assumption, ranging from the construction of quantum bit commitment schemes to the computational limitations of learning from quantum data.

Cite as

Alexander Poremba, Yihui Quek, and Peter Shor. The Learning Stabilizers with Noise Problem. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 108:1-108:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{poremba_et_al:LIPIcs.ITCS.2026.108,
  author =	{Poremba, Alexander and Quek, Yihui and Shor, Peter},
  title =	{{The Learning Stabilizers with Noise Problem}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{108:1--108:19},
  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.108},
  URN =		{urn:nbn:de:0030-drops-253950},
  doi =		{10.4230/LIPIcs.ITCS.2026.108},
  annote =	{Keywords: Random quantum stabilizer codes, average-case hardness}
}

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.TQC.2025.9

Efficient Quantum Pseudorandomness from Hamiltonian Phase States

Authors: John Bostanci, Jonas Haferkamp, Dominik Hangleiter, and Alexander Poremba

Published in: LIPIcs, Volume 350, 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)

Abstract

Quantum pseudorandomness has found applications in many areas of quantum information, ranging from entanglement theory, to models of scrambling phenomena in chaotic quantum systems, and, more recently, in the foundations of quantum cryptography. Kretschmer (TQC '21) showed that both pseudorandom states and pseudorandom unitaries exist even in a world without classical one-way functions. To this day, however, all known constructions require classical cryptographic building blocks which are themselves synonymous with the existence of one-way functions, and which are also challenging to implement on realistic quantum hardware. In this work, we seek to make progress on both of these fronts simultaneously - by decoupling quantum pseudorandomness from classical cryptography altogether. We introduce a quantum hardness assumption called the Hamiltonian Phase State (HPS) problem, which is the task of decoding output states of a random instantaneous quantum polynomial-time (IQP) circuit. Hamiltonian phase states can be generated very efficiently using only Hadamard gates, single-qubit Z rotations and CNOT circuits. We show that the hardness of our problem reduces to a worst-case version of the problem, and we provide evidence that our assumption is plausibly fully quantum; meaning, it cannot be used to construct one-way functions. We also show information-theoretic hardness when only few copies of HPS are available by proving an approximate t-design property of our ensemble. Finally, we show that our HPS assumption and its variants allow us to efficiently construct many pseudorandom quantum primitives, ranging from pseudorandom states, to quantum pseudoentanglement, to pseudorandom unitaries, and even primitives such as public-key encryption with quantum keys.

Cite as

John Bostanci, Jonas Haferkamp, Dominik Hangleiter, and Alexander Poremba. Efficient Quantum Pseudorandomness from Hamiltonian Phase States. In 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 350, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bostanci_et_al:LIPIcs.TQC.2025.9,
  author =	{Bostanci, John and Haferkamp, Jonas and Hangleiter, Dominik and Poremba, Alexander},
  title =	{{Efficient Quantum Pseudorandomness from Hamiltonian Phase States}},
  booktitle =	{20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)},
  pages =	{9:1--9:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-392-8},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{350},
  editor =	{Fefferman, Bill},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2025.9},
  URN =		{urn:nbn:de:0030-drops-240586},
  doi =		{10.4230/LIPIcs.TQC.2025.9},
  annote =	{Keywords: Quantum pseudorandomness, quantum phase states, quantum cryptography}
}

Document

DOI: 10.4230/LIPIcs.TQC.2025.10

Hamiltonian Locality Testing via Trotterized Postselection

Authors: John Kallaugher and Daniel Liang

Published in: LIPIcs, Volume 350, 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)

Abstract

The (tolerant) Hamiltonian locality testing problem, introduced in [Bluhm, Caro, Oufkir '24], is to determine whether a Hamiltonian H is ε₁-close to being k-local (i.e. can be written as the sum of weight-k Pauli operators) or ε₂-far from any k-local Hamiltonian, given access to its time evolution operator and using as little total evolution time as possible, with distance typically defined by the normalized Frobenius norm. We give the tightest known bounds for this problem, proving an O(√(ε₂/((ε₂-ε₁)⁵)) evolution time upper bound and an Ω(1/(ε₂-ε₁)) lower bound. Our algorithm does not require reverse time evolution or controlled application of the time evolution operator, although our lower bound applies to algorithms using either tool. Furthermore, we show that if we are allowed reverse time evolution, this lower bound is tight, giving a matching O(1/(ε₂-ε₁)) evolution time algorithm.

Cite as

John Kallaugher and Daniel Liang. Hamiltonian Locality Testing via Trotterized Postselection. In 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 350, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kallaugher_et_al:LIPIcs.TQC.2025.10,
  author =	{Kallaugher, John and Liang, Daniel},
  title =	{{Hamiltonian Locality Testing via Trotterized Postselection}},
  booktitle =	{20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-392-8},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{350},
  editor =	{Fefferman, Bill},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2025.10},
  URN =		{urn:nbn:de:0030-drops-240593},
  doi =		{10.4230/LIPIcs.TQC.2025.10},
  annote =	{Keywords: quantum algorithms, property testing, hamiltonians}
}

Document

DOI: 10.4230/LIPIcs.CCC.2025.20

Counting Martingales for Measure and Dimension in Complexity Classes

Authors: John M. Hitchcock, Adewale Sekoni, and Hadi Shafei

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract

This paper makes two primary contributions. First, we introduce the concept of counting martingales and use it to define counting measures and counting dimensions. Second, we apply these new tools to strengthen previous circuit lower bounds. Resource-bounded measure and dimension have traditionally focused on deterministic time and space bounds. We use counting complexity classes to develop resource-bounded counting measures and dimensions. Counting martingales are constructed using functions from the #𝖯, SpanP, and GapP complexity classes. We show that counting martingales capture many martingale constructions in complexity theory. The resulting counting measures and dimensions are intermediate in power between the standard time-bounded and space-bounded notions, enabling finer-grained analysis where space-bounded measures are known, but time-bounded measures remain open. For example, we show that BPP has #𝖯-dimension 0 and BQP has GapP-dimension 0, whereas the 𝖯-dimensions of these classes remain open. As our main application, we improve circuit-size lower bounds. Lutz (1992) strengthened Shannon’s classic (1-ε) 2ⁿ/n lower bound (1949) to PSPACE-measure, showing that almost all problems require circuits of size (2ⁿ/n)(1+(α log n)/n), for any α < 1. We extend this result to SpanP-measure, with a proof that uses a connection through the Minimum Circuit Size Problem (MCSP) to construct a counting martingale. Our results imply that the stronger lower bound holds within the third level of the exponential-time hierarchy, whereas previously, it was only known in ESPACE. Under a derandomization hypothesis, this lower bound holds within the second level of the exponential-time hierarchy, specifically in the class 𝖤^NP. We also study the #𝖯-dimension of classical circuit complexity classes and the GapP-dimension of quantum circuit complexity classes.

Cite as

John M. Hitchcock, Adewale Sekoni, and Hadi Shafei. Counting Martingales for Measure and Dimension in Complexity Classes. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 20:1-20:35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hitchcock_et_al:LIPIcs.CCC.2025.20,
  author =	{Hitchcock, John M. and Sekoni, Adewale and Shafei, Hadi},
  title =	{{Counting Martingales for Measure and Dimension in Complexity Classes}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{20:1--20:35},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.20},
  URN =		{urn:nbn:de:0030-drops-237145},
  doi =		{10.4230/LIPIcs.CCC.2025.20},
  annote =	{Keywords: resource-bounded measure, resource-bounded dimension, counting martingales, counting complexity, circuit complexity, Kolmogorov complexity, quantum complexity, Minimum Circuit Size Problem}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2025.9

On the Quantum Time Complexity of Divide and Conquer

Authors: Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, and Miklos Santha

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract

In this work, we initiate a systematic study of the time complexity of quantum divide and conquer (QD&C) algorithms for classical problems, and propose a general framework for their analysis. We establish generic conditions under which search and minimization problems with classical divide and conquer algorithms are amenable to quantum speedup, and apply these theorems to various problems involving strings, integers, and geometric objects. These include Longest Distinct Substring, Klee's Coverage, several optimization problems on stock transactions, and k-Increasing Subsequence. For most of these problems our quantum time upper bounds match the quantum query lower bounds, up to polylogarithmic factors. We give a structured framework for describing and classifying a wide variety of QD&C algorithms so that quantum speedups can be more easily identified and applied, and prove general statements on QD&C time complexity covering a range of cases, accounting for the time required for all operations. In particular, we explicitly account for memory access operations in the commonly used QRAM (read-only) and QRAG (read-write) models, which are assumed to take unit time in the query model, and which require careful analysis when involved in recursion. Our generic QD&C theorems have several nice features. 1) To apply them, it suffices to come up with a classical divide and conquer algorithm satisfying the conditions of the theorem. The quantization of the algorithm is then completely handled by the theorem. This can make it easier to find applications which admit a quantum speedup, and contrast with dynamic programming algorithms which can be difficult to quantize due to their highly sequential nature. 2) As these theorems give bounds on time complexity, they can be applied to a greater range of problems than those based on query complexity, e.g., where the best-known quantum algorithms require super-linear time. 3) It can handle minimization problems as well as boolean functions, which allows us to improve on the query complexity result of Childs et al. [Childs et al., 2025] for k-Increasing Subsequence by a logarithmic factor.

Cite as

Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, and Miklos Santha. On the Quantum Time Complexity of Divide and Conquer. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 9:1-9:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{allcock_et_al:LIPIcs.ICALP.2025.9,
  author =	{Allcock, Jonathan and Bao, Jinge and Belovs, Aleksandrs and Lee, Troy and Santha, Miklos},
  title =	{{On the Quantum Time Complexity of Divide and Conquer}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{9:1--9:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.9},
  URN =		{urn:nbn:de:0030-drops-233863},
  doi =		{10.4230/LIPIcs.ICALP.2025.9},
  annote =	{Keywords: Quantum Computing, Quantum Algorithms, Divide and Conquer}
}

Document

DOI: 10.4230/LIPIcs.STACS.2025.11

Generalized Inner Product Estimation with Limited Quantum Communication

Authors: Srinivasan Arunachalam and Louis Schatzki

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract

In this work, we consider the fundamental task of distributed inner product estimation when allowed limited communication. Suppose Alice and Bob are given k copies of an unknown n-qubit quantum state |ψ⟩,|ϕ⟩ respectively, are allowed to send q qubits to one another, and the task is to estimate |⟨ψ|ϕ⟩|² up to constant additive error. We show that k = Θ(√{2^{n-q}}) copies are essentially necessary and sufficient for this task (extending the work of Anshu, Landau and Liu (STOC'22) who considered the case when q = 0). Additionally, we also consider the task when the goal of the players is to estimate |⟨ψ|M|ϕ⟩|², for arbitrary Hermitian M. For this task we show that certain norms on M determine the sample complexity of estimating |⟨ψ|M|ϕ⟩|² when using only classical communication.

Cite as

Srinivasan Arunachalam and Louis Schatzki. Generalized Inner Product Estimation with Limited Quantum Communication. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.STACS.2025.11,
  author =	{Arunachalam, Srinivasan and Schatzki, Louis},
  title =	{{Generalized Inner Product Estimation with Limited Quantum Communication}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine 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.2025.11},
  URN =		{urn:nbn:de:0030-drops-228366},
  doi =		{10.4230/LIPIcs.STACS.2025.11},
  annote =	{Keywords: Quantum property testing, Quantum Distributed Algorithms}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2025.79

Catalytic Communication

Authors: Edward Pyne, Nathan S. Sheffield, and William Wang

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract

The study of space-bounded computation has drawn extensively from ideas and results in the field of communication complexity. Catalytic Computation (Buhrman, Cleve, Koucký, Loff and Speelman, STOC 2013) studies the power of bounded space augmented with a pre-filled hard drive that can be used non-destructively during the computation. Presently, many structural questions in this model remain open. Towards a better understanding of catalytic space, we define a model of catalytic communication complexity and prove new upper and lower bounds. In our model, Alice and Bob share a blackboard with a tiny number of free bits, and a larger section with an arbitrary initial configuration. They must jointly compute a function of their inputs, communicating only via the blackboard, and must always reset the blackboard to its initial configuration. We prove several upper and lower bounds: 1) We characterize the simplest nontrivial model, that of one bit of free space and three rounds, in terms of 𝔽₂ rank. In particular, we give natural problems that are solvable with a minimal-sized blackboard that require near-maximal (randomized) communication complexity, and vice versa. 2) We show that allowing constantly many free bits, as opposed to one, allows an exponential improvement on the size of the blackboard for natural problems. To do so, we connect the problem to existence questions in extremal graph theory. 3) We give tight connections between our model and standard notions of non-uniform catalytic computation. Using this connection, we show that with an arbitrary constant number of rounds and bits of free space, one can compute all functions in TC⁰. We view this model as a step toward understanding the value of filled space in computation.

Cite as

Edward Pyne, Nathan S. Sheffield, and William Wang. Catalytic Communication. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 79:1-79:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pyne_et_al:LIPIcs.ITCS.2025.79,
  author =	{Pyne, Edward and Sheffield, Nathan S. and Wang, William},
  title =	{{Catalytic Communication}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{79:1--79:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.79},
  URN =		{urn:nbn:de:0030-drops-227076},
  doi =		{10.4230/LIPIcs.ITCS.2025.79},
  annote =	{Keywords: Catalytic computation, Branching programs, Communication complexity}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2025.71

Toward the Impossibility of Perfect Complete Quantum PKE from OWFs

Authors: Longcheng Li, Qian Li, Xingjian Li, and Qipeng Liu

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract

In this paper, we study the impossibility of constructing perfect complete quantum public key encryption (QPKE) from quantumly secure one-way functions (OWFs) in a black-box manner. We show that this problem is connected to a fundamental conjecture about the roots of low-degree polynomials on the Boolean hypercube. Informally, the conjecture asserts that for every nonconstant low-degree polynomial, there exists a universal (randomized) way to modify a small number of input bits such that, for every input string, the polynomial evaluated on the modified input string avoids 0 with sufficiently large probability (over the choice of how the input string is modified). Assuming this conjecture, we demonstrate the impossibility of constructing QPKE from quantumly secure one-way functions in a black-box manner, by employing the information-theoretical approach recently developed by Li, Li, Li, and Liu (CRYPTO'24). Towards resolving this conjecture, we provide various pieces of evidence supporting it and prove some special cases. In particular, we fully rule out perfect QPKE from OWFs when the key generation algorithm only makes a logarithmic number of quantum queries, improving the previous work, which can only handle classical queries.

Cite as

Longcheng Li, Qian Li, Xingjian Li, and Qipeng Liu. Toward the Impossibility of Perfect Complete Quantum PKE from OWFs. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 71:1-71:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ITCS.2025.71,
  author =	{Li, Longcheng and Li, Qian and Li, Xingjian and Liu, Qipeng},
  title =	{{Toward the Impossibility of Perfect Complete Quantum PKE from OWFs}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{71:1--71:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.71},
  URN =		{urn:nbn:de:0030-drops-226999},
  doi =		{10.4230/LIPIcs.ITCS.2025.71},
  annote =	{Keywords: Qautnum public-key encryption, Boolean function analysis}
}

36 Search Results for "Arunachalam, Srinivasan"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message