13 Search Results for "Schaeffer, Luke"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.73
Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals

Authors: Daniel Grier, Daniel M. Kane, Jackson Morris, Anthony Ostuni, and Kewen Wu

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

Abstract
We construct a family of distributions {𝒟_n}_n with 𝒟_n over {0, 1}ⁿ and a family of depth-7 quantum circuits {C_n}_n such that 𝒟_n is produced exactly by C_n with the all zeros state as input, yet any constant-depth classical circuit with bounded fan-in gates evaluated on any binary product distribution has total variation distance 1 - e^{-Ω(n)} from 𝒟_n. Moreover, the quantum circuits we construct are geometrically local and use a relatively standard gate set: Hadamard, controlled-phase, CNOT, and Toffoli gates. All previous separations of this type suffer from some undesirable constraint on the classical circuit model or the quantum circuits witnessing the separation. Our family of distributions is inspired by the Parity Halving Problem of Watts, Kothari, Schaeffer, and Tal (STOC, 2019), which built on the work of Bravyi, Gosset, and König (Science, 2018) to separate shallow quantum and classical circuits for relational problems.
Cite as

Daniel Grier, Daniel M. Kane, Jackson Morris, Anthony Ostuni, and Kewen Wu. Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 73:1-73:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{grier_et_al:LIPIcs.ITCS.2026.73,
  author =	{Grier, Daniel and Kane, Daniel M. and Morris, Jackson and Ostuni, Anthony and Wu, Kewen},
  title =	{{Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{73:1--73:14},
  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.73},
  URN =		{urn:nbn:de:0030-drops-253607},
  doi =		{10.4230/LIPIcs.ITCS.2026.73},
  annote =	{Keywords: Shallow circuits, sampling, quantum circuits}
}
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.17
Unconditional Quantum Advantage for Sampling with Shallow Circuits

Authors: Adam Bene Watts and Natalie Parham

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

Abstract
Recent work by Bravyi, Gosset, and Koenig showed that there exists a search problem that a constant-depth quantum circuit can solve, but that any constant-depth classical circuit with bounded fan-in cannot. They also pose the question: Can we achieve a similar proof of separation for an input-independent sampling task? In this paper, we show that the answer to this question is yes when the number of random input bits given to the classical circuit is bounded. We introduce a distribution D_{n} over {0,1}ⁿ and construct a constant-depth uniform quantum circuit family {C_n}_n such that C_n samples from a distribution close to D_{n} in total variation distance. For any δ < 1 we also prove, unconditionally, that any classical circuit with bounded fan-in gates that takes as input kn + n^δ i.i.d. Bernouli random variables with entropy 1/k and produces output close to D_{n} in total variation distance has depth Ω(log log n). This gives an unconditional proof that constant-depth quantum circuits can sample from distributions that can't be reproduced by constant-depth bounded fan-in classical circuits, even up to additive error. We also show a similar separation between constant-depth quantum circuits with advice and classical circuits with bounded fan-in and fan-out, but access to an unbounded number of i.i.d random inputs. The distribution D_n and classical circuit lower bounds are inspired by work of Viola, in which he shows a different (but related) distribution cannot be sampled from approximately by constant-depth bounded fan-in classical circuits.
Cite as

Adam Bene Watts and Natalie Parham. Unconditional Quantum Advantage for Sampling with Shallow Circuits. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 17:1-17:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{benewatts_et_al:LIPIcs.ITCS.2026.17,
  author =	{Bene Watts, Adam and Parham, Natalie},
  title =	{{Unconditional Quantum Advantage for Sampling with Shallow Circuits}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{17:1--17:12},
  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.17},
  URN =		{urn:nbn:de:0030-drops-253048},
  doi =		{10.4230/LIPIcs.ITCS.2026.17},
  annote =	{Keywords: Circuit Complexity, Sampling Separation, Shallow Quantum Circuits, Unconditional Separations, Complexity of Distributions}
}
Document
DOI: 10.4230/OASIcs.Manzini.1
BWT and Combinatorics on Words

Authors: Gabriele Fici, Sabrina Mantaci, Antonio Restivo, Giuseppe Romana, Giovanna Rosone, and Marinella Sciortino

Published in: OASIcs, Volume 131, The Expanding World of Compressed Data: A Festschrift for Giovanni Manzini's 60th Birthday (2025)

Abstract
The Burrows-Wheeler Transform (BWT) is a reversible transformation on words (strings) introduced in 1994 in the context of data compression, which is a permutation of the characters in the word. Its clustering effect, i.e., the remarkable property of grouping identical characters (BWT runs) when they share common contexts, has made it a powerful tool for boosting compression performances and enabling efficient pattern searching in highly repetitive string collections. In this chapter, we analyze the Burrows-Wheeler transform under the combinatorial point of view, and we survey known properties and connections with different aspects of combinatorics on words. In particular, we focus on the properties of words in relation to the number of their BWT runs. The value r, which counts the number of BWT runs, impacts both compression performance and indexing efficiency, and is considered a measure to evaluate the above-mentioned clustering effect and, consequently, the repetitiveness of a word. We give an overview of the results relating r to other combinatorial repetitiveness measures related to the factor complexity. The chapter also explores extremal cases of the clustering effect. Finally, some results on the sensitivity of the measure r are considered, where the effects of combinatorial operations are studied, such as reversal, edits, and the application of morphisms.
Cite as

Gabriele Fici, Sabrina Mantaci, Antonio Restivo, Giuseppe Romana, Giovanna Rosone, and Marinella Sciortino. BWT and Combinatorics on Words. In The Expanding World of Compressed Data: A Festschrift for Giovanni Manzini's 60th Birthday. Open Access Series in Informatics (OASIcs), Volume 131, pp. 1:1-1:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fici_et_al:OASIcs.Manzini.1,
  author =	{Fici, Gabriele and Mantaci, Sabrina and Restivo, Antonio and Romana, Giuseppe and Rosone, Giovanna and Sciortino, Marinella},
  title =	{{BWT and Combinatorics on Words}},
  booktitle =	{The Expanding World of Compressed Data: A Festschrift for Giovanni Manzini's 60th Birthday},
  pages =	{1:1--1:23},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-390-4},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{131},
  editor =	{Ferragina, Paolo and Gagie, Travis and Navarro, Gonzalo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Manzini.1},
  URN =		{urn:nbn:de:0030-drops-239090},
  doi =		{10.4230/OASIcs.Manzini.1},
  annote =	{Keywords: Burrows-Wheeler Transform, Combinatorics on Words, Clustering Effect, BWT Runs}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.3
Quantum Threshold Is Powerful

Authors: Daniel Grier and Jackson Morris

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

Abstract
In 2005, Høyer and Špalek showed that constant-depth quantum circuits augmented with multi-qubit Fanout gates are quite powerful, able to compute a wide variety of Boolean functions as well as the quantum Fourier transform. They also asked what other multi-qubit gates could rival Fanout in terms of computational power, and suggested that the quantum Threshold gate might be one such candidate. Threshold is the gate that indicates if the Hamming weight of a classical basis state input is greater than some target value. We prove that Threshold is indeed powerful - there are polynomial-size constant-depth quantum circuits with Threshold gates that compute Fanout to high fidelity. Our proof is a generalization of a proof by Rosenthal that exponential-size constant-depth circuits with generalized Toffoli gates can compute Fanout. Our construction reveals that other quantum gates able to "weakly approximate" Parity can also be used as substitutes for Fanout.
Cite as

Daniel Grier and Jackson Morris. Quantum Threshold Is Powerful. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 3:1-3:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{grier_et_al:LIPIcs.CCC.2025.3,
  author =	{Grier, Daniel and Morris, Jackson},
  title =	{{Quantum Threshold Is Powerful}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{3:1--3:23},
  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.3},
  URN =		{urn:nbn:de:0030-drops-236979},
  doi =		{10.4230/LIPIcs.CCC.2025.3},
  annote =	{Keywords: Shallow Quantum Circuits, Circuit Complexity, Threshold Circuits}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.89
On the Complexity of Client-Waiter and Waiter-Client Games

Authors: Valentin Gledel, Nacim Oijid, Sébastien Tavenas, and Stéphan Thomassé

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

Abstract
Positional games were introduced by Hales and Jewett in 1963, and their study became more popular when Erdős and Selfridge showed their connection to Ramsey theory and hypergraph coloring in 1973. Several conventions of these games exist, and the most popular one, Maker-Breaker was proved to be PSPACE-complete by Schaefer in 1978. The study of their complexity then stopped for decades, until 2017 when Bonnet, Jamain, and Saffidine proved that Maker-Breaker is W[1]-complete when parameterized by the number of moves. The study was then intensified when Rahman and Watson improved Schaefer’s result in 2021 by proving that the PSPACE-hardness holds for 6-uniform hypergraphs. More recently, Galliot, Gravier, and Sivignon proved that computing the winner on rank 3 hypergraphs is in P, and Keopke proved that the PSPACE-hardness also holds for 5-uniform hypergraphs. We focus here on the Client-Waiter and the Waiter-Client conventions. Both were proved to be NP-hard by Csernenszky, Martin, and Pluhár in 2011, but neither completeness nor positive results were known. In this paper, we complete the study of these conventions by proving that the former is PSPACE-complete, even restricted to 6-uniform hypergraphs, and by providing an FPT-algorithm for the latter, parameterized by the size of its largest edge. In particular, the winner of Waiter-Client can be computed in polynomial time in rank k hypergraphs for any fixed integer k. Finally, in search of the exact location of the complexity gap in the Client-Waiter convention, we focus on rank 3 hypergraphs. We provide an algorithm that runs in polynomial time with an oracle in NP.
Cite as

Valentin Gledel, Nacim Oijid, Sébastien Tavenas, and Stéphan Thomassé. On the Complexity of Client-Waiter and Waiter-Client Games. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 89:1-89:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gledel_et_al:LIPIcs.ICALP.2025.89,
  author =	{Gledel, Valentin and Oijid, Nacim and Tavenas, S\'{e}bastien and Thomass\'{e}, St\'{e}phan},
  title =	{{On the Complexity of Client-Waiter and Waiter-Client Games}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{89:1--89:18},
  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.89},
  URN =		{urn:nbn:de:0030-drops-234666},
  doi =		{10.4230/LIPIcs.ICALP.2025.89},
  annote =	{Keywords: Complexity, positional games, Maker-Breaker, Client-Waiter, Waiter-Client, PSPACE-complete, FPT}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.31
Quantum Advantage and Lower Bounds in Parallel Query Complexity

Authors: Joseph Carolan, Amin Shiraz Gilani, and Mahathi Vempati

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

Abstract
It is well known that quantum, randomized and deterministic (sequential) query complexities are polynomially related for total boolean functions. We find that significantly larger separations between the parallel generalizations of these measures are possible. In particular, 1) We employ the cheatsheet framework to obtain an unbounded parallel quantum query advantage over its randomized analogue for a total function, falsifying a conjecture of [https://arxiv.org/abs/1309.6116]. 2) We strengthen 1 by constructing a total function which exhibits an unbounded parallel quantum query advantage despite having no sequential advantage, suggesting that genuine quantum advantage could occur entirely due to parallelism. 3) We construct a total function that exhibits a polynomial separation between 2-round quantum and randomized query complexities, contrasting a result of [https://arxiv.org/abs/1001.0018] that there is at most a constant separation for 1-round (nonadaptive) algorithms. 4) We develop a new technique for deriving parallel quantum lower bounds from sequential upper bounds. We employ this technique to give lower bounds for Boolean symmetric functions and read-once formulas, ruling out large parallel query advantages for them. We also provide separations between randomized and deterministic parallel query complexities analogous to items 1-3.
Cite as

Joseph Carolan, Amin Shiraz Gilani, and Mahathi Vempati. Quantum Advantage and Lower Bounds in Parallel Query Complexity. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{carolan_et_al:LIPIcs.ITCS.2025.31,
  author =	{Carolan, Joseph and Gilani, Amin Shiraz and Vempati, Mahathi},
  title =	{{Quantum Advantage and Lower Bounds in Parallel Query Complexity}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{31:1--31:14},
  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.31},
  URN =		{urn:nbn:de:0030-drops-226597},
  doi =		{10.4230/LIPIcs.ITCS.2025.31},
  annote =	{Keywords: Computational complexity theory, quantum, lower bounds, parallel}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.32
Succinct Fermion Data Structures

Authors: Joseph Carolan and Luke Schaeffer

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

Abstract
Simulating fermionic systems on a quantum computer requires representing fermionic states using qubits. The complexity of many simulation algorithms depends on the complexity of implementing rotations generated by fermionic creation-annihilation operators, and the space depends on the number of qubits used. While standard fermion encodings like Jordan-Wigner are space optimal for arbitrary fermionic systems, physical symmetries like particle conservation can reduce the number of physical configurations, allowing improved space complexity. Such space saving is only feasible if the gate overhead is small, suggesting a (quantum) data structures problem, wherein one would like to minimize space used to represent a fermionic state, while still enabling efficient rotations. We define a structure which naturally captures mappings from fermions to systems of qubits. We then instantiate it in two ways, giving rise to two new second-quantized fermion encodings of F fermions in M modes. An information theoretic minimum of I: = ⌈log₂ binom(M,F)⌉ qubits is required for such systems, a bound we nearly match over the entire parameter regime. 1) Our first construction uses I + o(I) qubits when F = o(M), and allows rotations generated by creation-annihilation operators in O(I) gates and O(log M log log M) depth. 2) Our second construction uses I + O(1) qubits when F = Θ(M), and allows rotations generated by creation-annihilation operators in O(I³) gates. In relation to comparable prior work, the first represents a polynomial improvement in both space and gate complexity (against Kirby et al. 2022), and the second represents an exponential improvement in gate complexity at the cost of only a constant number of additional qubits (against Harrison et al. or Shee et al. 2022), in the described parameter regimes.
Cite as

Joseph Carolan and Luke Schaeffer. Succinct Fermion Data Structures. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 32:1-32:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{carolan_et_al:LIPIcs.ITCS.2025.32,
  author =	{Carolan, Joseph and Schaeffer, Luke},
  title =	{{Succinct Fermion Data Structures}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{32:1--32:21},
  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.32},
  URN =		{urn:nbn:de:0030-drops-226600},
  doi =		{10.4230/LIPIcs.ITCS.2025.32},
  annote =	{Keywords: quantum computing, data structures, fermion encodings}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.97
Quantum Event Learning and Gentle Random Measurements

Authors: Adam Bene Watts and John Bostanci

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We prove the expected disturbance caused to a quantum system by a sequence of randomly ordered two-outcome projective measurements is upper bounded by the square root of the probability that at least one measurement in the sequence accepts. We call this bound the Gentle Random Measurement Lemma. We then extend the techniques used to prove this lemma to develop protocols for problems in which we are given sample access to an unknown state ρ and asked to estimate properties of the accepting probabilities Tr[M_i ρ] of a set of measurements {M₁, M₂, … , M_m}. We call these types of problems Quantum Event Learning Problems. In particular, we show randomly ordering projective measurements solves the Quantum OR problem, answering an open question of Aaronson. We also give a Quantum OR protocol which works on non-projective measurements and which outperforms both the random measurement protocol analyzed in this paper and the protocol of Harrow, Lin, and Montanaro. However, this protocol requires a more complicated type of measurement, which we call a Blended Measurement. Given additional guarantees on the set of measurements {M₁, …, M_m}, we show the random and blended measurement Quantum OR protocols developed in this paper can also be used to find a measurement M_i such that Tr[M_i ρ] is large. We call the problem of finding such a measurement Quantum Event Finding. We also show Blended Measurements give a sample-efficient protocol for Quantum Mean Estimation: a problem in which the goal is to estimate the average accepting probability of a set of measurements on an unknown state. Finally we consider the Threshold Search Problem described by O'Donnell and Bădescu where, given given a set of measurements {M₁, …, M_m} along with sample access to an unknown state ρ satisfying Tr[M_i ρ] ≥ 1/2 for some M_i, the goal is to find a measurement M_j such that Tr[M_j ρ] ≥ 1/2 - ε. By building on our Quantum Event Finding result we show that randomly ordered (or blended) measurements can be used to solve this problem using O(log²(m) / ε²) copies of ρ. This matches the performance of the algorithm given by O'Donnell and Bădescu, but does not require injected noise in the measurements. Consequently, we obtain an algorithm for Shadow Tomography which matches the current best known sample complexity (i.e. requires Õ(log²(m)log(d)/ε⁴) samples). This algorithm does not require injected noise in the quantum measurements, but does require measurements to be made in a random order, and so is no longer online.
Cite as

Adam Bene Watts and John Bostanci. Quantum Event Learning and Gentle Random Measurements. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 97:1-97:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{watts_et_al:LIPIcs.ITCS.2024.97,
  author =	{Watts, Adam Bene and Bostanci, John},
  title =	{{Quantum Event Learning and Gentle Random Measurements}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{97:1--97:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.97},
  URN =		{urn:nbn:de:0030-drops-196254},
  doi =		{10.4230/LIPIcs.ITCS.2024.97},
  annote =	{Keywords: Event learning, gentle measurments, random measurements, quantum or, threshold search, shadow tomography}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.CPM.2022.2
Using Automata and a Decision Procedure to Prove Results in Pattern Matching (Invited Talk)

Authors: Jeffrey Shallit

Published in: LIPIcs, Volume 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)

Abstract
The first-order theory of automatic sequences with addition is decidable, and this means that one can often prove combinatorial properties of these sequences "automatically", using the free software Walnut written by Hamoon Mousavi. In this talk I will explain how this is done, using as an example the measure of minimize size string attractor, introduced by Kempa and Prezza in 2018. Using the logic-based approach, we can also prove more general properties of string attractors for automatic sequences. This is joint work with Luke Schaeffer.
Cite as

Jeffrey Shallit. Using Automata and a Decision Procedure to Prove Results in Pattern Matching (Invited Talk). In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 223, pp. 2:1-2:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{shallit:LIPIcs.CPM.2022.2,
  author =	{Shallit, Jeffrey},
  title =	{{Using Automata and a Decision Procedure to Prove Results in Pattern Matching}},
  booktitle =	{33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)},
  pages =	{2:1--2:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-234-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{223},
  editor =	{Bannai, Hideo and Holub, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.2},
  URN =		{urn:nbn:de:0030-drops-161297},
  doi =		{10.4230/LIPIcs.CPM.2022.2},
  annote =	{Keywords: finite automata, decision procedure, automatic sequence, Thue-Morse sequence, Fibonacci word, string attractor}
}
Document
DOI: 10.4230/LIPIcs.CSL.2022.24
Decidability for Sturmian Words

Authors: Philipp Hieronymi, Dun Ma, Reed Oei, Luke Schaeffer, Christian Schulz, and Jeffrey Shallit

Published in: LIPIcs, Volume 216, 30th EACSL Annual Conference on Computer Science Logic (CSL 2022)

Abstract
We show that the first-order theory of Sturmian words over Presburger arithmetic is decidable. Using a general adder recognizing addition in Ostrowski numeration systems by Baranwal, Schaeffer and Shallit, we prove that the first-order expansions of Presburger arithmetic by a single Sturmian word are uniformly ω-automatic, and then deduce the decidability of the theory of the class of such structures. Using an implementation of this decision algorithm called Pecan, we automatically reprove classical theorems about Sturmian words in seconds, and are able to obtain new results about antisquares and antipalindromes in characteristic Sturmian words.
Cite as

Philipp Hieronymi, Dun Ma, Reed Oei, Luke Schaeffer, Christian Schulz, and Jeffrey Shallit. Decidability for Sturmian Words. In 30th EACSL Annual Conference on Computer Science Logic (CSL 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 216, pp. 24:1-24:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hieronymi_et_al:LIPIcs.CSL.2022.24,
  author =	{Hieronymi, Philipp and Ma, Dun and Oei, Reed and Schaeffer, Luke and Schulz, Christian and Shallit, Jeffrey},
  title =	{{Decidability for Sturmian Words}},
  booktitle =	{30th EACSL Annual Conference on Computer Science Logic (CSL 2022)},
  pages =	{24:1--24:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-218-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{216},
  editor =	{Manea, Florin and Simpson, Alex},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2022.24},
  URN =		{urn:nbn:de:0030-drops-157440},
  doi =		{10.4230/LIPIcs.CSL.2022.24},
  annote =	{Keywords: Decidability, Sturmian words, Ostrowski numeration systems, Automated theorem proving}
}
Document
DOI: 10.4230/LIPIcs.CCC.2018.19
New Hardness Results for the Permanent Using Linear Optics

Authors: Daniel Grier and Luke Schaeffer

Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)

Abstract
In 2011, Aaronson gave a striking proof, based on quantum linear optics, that the problem of computing the permanent of a matrix is #P-hard. Aaronson's proof led naturally to hardness of approximation results for the permanent, and it was arguably simpler than Valiant's seminal proof of the same fact in 1979. Nevertheless, it did not show #P-hardness of the permanent for any class of matrices which was not previously known. In this paper, we present a collection of new results about matrix permanents that are derived primarily via these linear optical techniques. First, we show that the problem of computing the permanent of a real orthogonal matrix is #P-hard. Much like Aaronson's original proof, this implies that even a multiplicative approximation remains #P-hard to compute. The hardness result even translates to permanents of orthogonal matrices over the finite field F_{p^4} for p != 2, 3. Interestingly, this characterization is tight: in fields of characteristic 2, the permanent coincides with the determinant; in fields of characteristic 3, one can efficiently compute the permanent of an orthogonal matrix by a nontrivial result of Kogan. Finally, we use more elementary arguments to prove #P-hardness for the permanent of a positive semidefinite matrix. This result shows that certain probabilities of boson sampling experiments with thermal states are hard to compute exactly, despite the fact that they can be efficiently sampled by a classical computer.
Cite as

Daniel Grier and Luke Schaeffer. New Hardness Results for the Permanent Using Linear Optics. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 19:1-19:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{grier_et_al:LIPIcs.CCC.2018.19,
  author =	{Grier, Daniel and Schaeffer, Luke},
  title =	{{New Hardness Results for the Permanent Using Linear Optics}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{19:1--19:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Servedio, Rocco A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.19},
  URN =		{urn:nbn:de:0030-drops-88702},
  doi =		{10.4230/LIPIcs.CCC.2018.19},
  annote =	{Keywords: Permanent, Linear optics, #P-hardness, Orthogonal matrices}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2017.23
The Classification of Reversible Bit Operations

Authors: Scott Aaronson, Daniel Grier, and Luke Schaeffer

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Abstract
We present a complete classification of all possible sets of classical reversible gates acting on bits, in terms of which reversible transformations they generate, assuming swaps and ancilla bits are available for free. Our classification can be seen as the reversible-computing analogue of Post's lattice, a central result in mathematical logic from the 1940s. It is a step toward the ambitious goal of classifying all possible quantum gate sets acting on qubits. Our theorem implies a linear-time algorithm (which we have implemented), that takes as input the truth tables of reversible gates G and H, and that decides whether G generates H. Previously, this problem was not even known to be decidable (though with effort, one can derive from abstract considerations an algorithm that takes triply-exponential time). The theorem also implies that any n-bit reversible circuit can be "compressed" to an equivalent circuit, over the same gates, that uses at most 2^{n}poly(n) gates and O(1) ancilla bits; these are the first upper bounds on these quantities known, and are close to optimal. Finally, the theorem implies that every non-degenerate reversible gate can implement either every reversible transformation, or every affine transformation, when restricted to an "encoded subspace." Briefly, the theorem says that every set of reversible gates generates either all reversible transformations on n-bit strings (as the Toffoli gate does); no transformations; all transformations that preserve Hamming weight (as the Fredkin gate does); all transformations that preserve Hamming weight mod k for some k; all affine transformations (as the Controlled-NOT gate does); all affine transformations that preserve Hamming weight mod 2 or mod 4, inner products mod 2, or a combination thereof; or a previous class augmented by a NOT or NOTNOT gate. Prior to this work, it was not even known that every class was finitely generated. Ruling out the possibility of additional classes, not in the list, requires involved arguments about polynomials, lattices, and Diophantine equations.
Cite as

Scott Aaronson, Daniel Grier, and Luke Schaeffer. The Classification of Reversible Bit Operations. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 23:1-23:34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{aaronson_et_al:LIPIcs.ITCS.2017.23,
  author =	{Aaronson, Scott and Grier, Daniel and Schaeffer, Luke},
  title =	{{The Classification of Reversible Bit Operations}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{23:1--23:34},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.23},
  URN =		{urn:nbn:de:0030-drops-81737},
  doi =		{10.4230/LIPIcs.ITCS.2017.23},
  annote =	{Keywords: Reversible computation, Reversible gates, Circuit synthesis, Gate classification, Boolean logic, Post’s lattice}
}
  • Refine by Type
  • 13 Document/PDF
  • 8 Document/HTML

  • Refine by Publication Year
  • 3 2026
  • 5 2025
  • 1 2024
  • 2 2022
  • 1 2018
  • Show More...

  • Refine by Author
  • 4 Grier, Daniel
  • 4 Schaeffer, Luke
  • 2 Carolan, Joseph
  • 2 Morris, Jackson
  • 2 Shallit, Jeffrey
  • Show More...

  • Refine by Series/Journal
  • 12 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 5 Theory of computation → Quantum complexity theory
  • 3 Theory of computation → Circuit complexity
  • 2 Mathematics of computing → Combinatorial algorithms
  • 2 Theory of computation → Complexity classes
  • 2 Theory of computation → Data compression
  • Show More...

  • Refine by Keyword
  • 2 Circuit Complexity
  • 2 Shallow Quantum Circuits
  • 1 #P-hardness
  • 1 Automated theorem proving
  • 1 BWT Runs
  • 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