5 Search Results for "Schaeffer, Luke"

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-dev.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-dev.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-dev.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-dev.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-dev.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 Author
  • 3 Schaeffer, Luke
  • 2 Grier, Daniel
  • 2 Shallit, Jeffrey
  • 1 Aaronson, Scott
  • 1 Bostanci, John
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Logic and verification
  • 1 Mathematics of computing → Combinatorics on words
  • 1 Theory of computation
  • 1 Theory of computation → Problems, reductions and completeness
  • 1 Theory of computation → Quantum computation theory
  • Show More...

  • Refine by Keyword
  • 1 #P-hardness
  • 1 Automated theorem proving
  • 1 Boolean logic
  • 1 Circuit synthesis
  • 1 Decidability
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2022
  • 1 2017
  • 1 2018
  • 1 2024

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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