32 Search Results for "Fawzi, Omar"

Volume

LIPIcs, Volume 266

18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)

TQC 2023, July 24-28, 2023, Aveiro, Portugal

Editors: Omar Fawzi and Michael Walter

Document
DOI: 10.4230/LIPIcs.ITCS.2026.57
Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits

Authors: Bill Fefferman, Soumik Ghosh, and Wei Zhan

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

Abstract
We prove a Carbery-Wright style anti-concentration inequality for the unitary Haar measure, by showing that the probability of a polynomial in the entries of a random unitary falling into an ε range is at most a polynomial in ε. Using it, we show that the scrambling speed of a random quantum circuit is lower bounded: Namely, every input qubit has an influence that is at least inverse exponential in depth, on any output qubit touched by its lightcone. Our result on scrambling speed works with high probability over the choice of a circuit from an ensemble, as opposed to just working in expectation. As an application, we give the first polynomial-time algorithm for learning log-depth random quantum circuits with Haar random gates up to polynomially small diamond distance, given oracle access to the circuit. Other applications of this new scrambling speed lower bound include: - An optimal Ω(log ε^{-1}) depth lower bound for ε-approximate unitary designs on any circuit architecture; - A polynomial-time quantum algorithm that computes the depth of a bounded-depth circuit, given oracle access to the circuit. Our learning and depth-testing algorithms apply to architectures defined over any geometric dimension, and can be generalized to a wide class of architectures with good lightcone properties.
Cite as

Bill Fefferman, Soumik Ghosh, and Wei Zhan. Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 57:1-57:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fefferman_et_al:LIPIcs.ITCS.2026.57,
  author =	{Fefferman, Bill and Ghosh, Soumik and Zhan, Wei},
  title =	{{Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{57:1--57:24},
  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.57},
  URN =		{urn:nbn:de:0030-drops-253443},
  doi =		{10.4230/LIPIcs.ITCS.2026.57},
  annote =	{Keywords: Haar measure, anti-concentration, random quanytum circuit, learning}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.25
Commuting Local Hamiltonians Beyond 2D

Authors: John Bostanci and Yeongwoo Hwang

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

Abstract
Commuting local Hamiltonians provide a testing ground for studying many of the most interesting open questions in quantum information theory, including the quantum PCP conjecture and the nature of entanglement. However, unlike the general local Hamiltonian problem, the exact complexity of the commuting local Hamiltonian problem (CLH) remains unknown. A number of works have shown that increasingly expressive families of commuting local Hamiltonians admit classical verifiers. Despite intense work, proofs placing CLH in NP rely heavily on an underlying 2D lattice structure, or a very constrained local dimension and locality. In this work, we present a new technique to analyze the complexity of various families of commuting local Hamiltonians: guided reductions. Intuitively, these are a generalization of typical reduction where the prover provides a guide so that the verifier can construct a simpler Hamiltonian. The core of our reduction is a new rounding technique based on a combination of Jordan’s Lemma for pairs of projectors and the Structure Lemma for C^* algebras. Our rounding technique is much more flexible than previous work and allows us to remove constraints on local dimension in exchange for a rank-1 assumption. Using our rounding technique, we prove the following two results: 1) 2D-CLH for rank-1 instances are contained in NP, independent of the qudit dimension. It is notable that this family of commuting local Hamiltonians has no restriction on the local dimension or the locality of the Hamiltonian terms. 2) 3D-CLH for rank-1 instances are in NP. To our knowledge this is the first time a family of {3D} commuting local Hamiltonians has been contained in NP. Our results apply to Hamiltonians with large qudit degree and remain non-trivial despite the quantum Lovász Local Lemma. [Andris Ambainis et al., 2012]
Cite as

John Bostanci and Yeongwoo Hwang. Commuting Local Hamiltonians Beyond 2D. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 25:1-25:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bostanci_et_al:LIPIcs.ITCS.2026.25,
  author =	{Bostanci, John and Hwang, Yeongwoo},
  title =	{{Commuting Local Hamiltonians Beyond 2D}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{25:1--25:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.25},
  URN =		{urn:nbn:de:0030-drops-253129},
  doi =		{10.4230/LIPIcs.ITCS.2026.25},
  annote =	{Keywords: Quantum complexity, commuting Hamiltonians, complexity theory, C* algebras}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.26
Local Transformations of Bipartite Entanglement Are Rigid

Authors: John Bostanci, Tony Metger, and Henry Yuen

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

Abstract
Uhlmann’s theorem is a fundamental result in quantum information theory that quantifies the optimal overlap between two bipartite pure states after applying local unitary operations (called Uhlmann transformations). We show that optimal Uhlmann transformations are rigid - in other words, they must be unique up to some well-characterized degrees of freedom. This rigidity is also robust: Uhlmann transformations achieving near-optimal overlaps must be close to the unique optimal transformation (again, up to well-characterized degrees of freedom). We describe two applications of our robust rigidity theorem: (a) we obtain better interactive proofs for synthesizing Uhlmann transformations and (b) we obtain a simple, alternative proof of the Gowers-Hatami theorem on the stability of approximate representations of finite groups.
Cite as

John Bostanci, Tony Metger, and Henry Yuen. Local Transformations of Bipartite Entanglement Are Rigid. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 26:1-26:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bostanci_et_al:LIPIcs.ITCS.2026.26,
  author =	{Bostanci, John and Metger, Tony and Yuen, Henry},
  title =	{{Local Transformations of Bipartite Entanglement Are Rigid}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{26:1--26: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.26},
  URN =		{urn:nbn:de:0030-drops-253138},
  doi =		{10.4230/LIPIcs.ITCS.2026.26},
  annote =	{Keywords: Uhlmann’s theorem, quantum entanglement, stability theorems}
}
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.1
Quantum Search with In-Place Queries

Authors: Blake Holman, Ronak Ramachandran, and Justin Yirka

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

Abstract
Quantum query complexity is typically characterized in terms of xor queries |x,y⟩ ↦ |x,y⊕ f(x)⟩ or phase queries, which ensure that even queries to non-invertible functions are unitary. When querying a permutation, another natural model is unitary: in-place queries |x⟩↦ |f(x)⟩. Some problems are known to require exponentially fewer in-place queries than xor queries, but no separation has been shown in the opposite direction. A candidate for such a separation was the problem of inverting a permutation over N elements. This task, equivalent to unstructured search in the context of permutations, is solvable with O(√N) xor queries but was conjectured to require Ω(N) in-place queries. We refute this conjecture by designing a quantum algorithm for Permutation Inversion using O(√N) in-place queries. Our algorithm achieves the same speedup as Grover’s algorithm despite the inability to efficiently uncompute queries or perform straightforward oracle-controlled reflections. Nonetheless, we show that there are indeed problems which require fewer xor queries than in-place queries. We introduce a subspace-conversion problem called Function Erasure that requires 1 xor query and Θ(√N) in-place queries. Then, we build on a recent extension of the quantum adversary method to characterize exact conditions for a decision problem to exhibit such a separation, and we propose a candidate problem.
Cite as

Blake Holman, Ronak Ramachandran, and Justin Yirka. Quantum Search with In-Place Queries. In 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 350, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{holman_et_al:LIPIcs.TQC.2025.1,
  author =	{Holman, Blake and Ramachandran, Ronak and Yirka, Justin},
  title =	{{Quantum Search with In-Place Queries}},
  booktitle =	{20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)},
  pages =	{1:1--1: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.1},
  URN =		{urn:nbn:de:0030-drops-240502},
  doi =		{10.4230/LIPIcs.TQC.2025.1},
  annote =	{Keywords: Quantum algorithms, query complexity, quantum complexity theory, quantum search, Grover’s algorithm, permutation inversion}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.16
On Fault Tolerant Single-Shot Logical State Preparation and Robust Long-Range Entanglement

Authors: Thiago Bergamaschi and Yunchao Liu

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

Abstract
Preparing encoded logical states is the first step in a fault-tolerant quantum computation. Standard approaches based on concatenation or repeated measurement incur a significant time overhead. The Raussendorf-Bravyi-Harrington cluster state [Raussendorf et al., 2005] offers an alternative: a single-shot preparation of encoded states of the surface code, by means of a constant depth quantum circuit, followed by a single round of measurement and classical feedforward [Bravyi et al., 2020]. In this work we generalize this approach and prove that single-shot logical state preparation can be achieved for arbitrary quantum LDPC codes. Our proof relies on a minimum-weight decoder and is based on a generalization of Gottesman’s clustering-of-errors argument [Gottesman, 2014]. As an application, we also prove single-shot preparation of the encoded GHZ state in arbitrary quantum LDPC codes. This shows that adaptive noisy constant depth quantum circuits are capable of generating generic robust long-range entanglement.
Cite as

Thiago Bergamaschi and Yunchao Liu. On Fault Tolerant Single-Shot Logical State Preparation and Robust Long-Range Entanglement. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 16:1-16:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bergamaschi_et_al:LIPIcs.ITCS.2025.16,
  author =	{Bergamaschi, Thiago and Liu, Yunchao},
  title =	{{On Fault Tolerant Single-Shot Logical State Preparation and Robust Long-Range Entanglement}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{16:1--16:9},
  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.16},
  URN =		{urn:nbn:de:0030-drops-226444},
  doi =		{10.4230/LIPIcs.ITCS.2025.16},
  annote =	{Keywords: Quantum error correction, fault tolerance, single-shot error correction, logical state preparation}
}
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}
}
Document
Academic Track
DOI: 10.4230/OASIcs.SAIA.2024.1
On Assessing ML Model Robustness: A Methodological Framework (Academic Track)

Authors: Afef Awadid and Boris Robert

Published in: OASIcs, Volume 126, Symposium on Scaling AI Assessments (SAIA 2024)

Abstract
Due to their uncertainty and vulnerability to adversarial attacks, machine learning (ML) models can lead to severe consequences, including the loss of human life, when embedded in safety-critical systems such as autonomous vehicles. Therefore, it is crucial to assess the empirical robustness of such models before integrating them into these systems. ML model robustness refers to the ability of an ML model to be insensitive to input perturbations and maintain its performance. Against this background, the Confiance.ai research program proposes a methodological framework for assessing the empirical robustness of ML models. The framework encompasses methodological processes (guidelines) captured in Capella models, along with a set of supporting tools. This paper aims to provide an overview of this framework and its application in an industrial setting.
Cite as

Afef Awadid and Boris Robert. On Assessing ML Model Robustness: A Methodological Framework (Academic Track). In Symposium on Scaling AI Assessments (SAIA 2024). Open Access Series in Informatics (OASIcs), Volume 126, pp. 1:1-1:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{awadid_et_al:OASIcs.SAIA.2024.1,
  author =	{Awadid, Afef and Robert, Boris},
  title =	{{On Assessing ML Model Robustness: A Methodological Framework}},
  booktitle =	{Symposium on Scaling AI Assessments (SAIA 2024)},
  pages =	{1:1--1:10},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-357-7},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{126},
  editor =	{G\"{o}rge, Rebekka and Haedecke, Elena and Poretschkin, Maximilian and Schmitz, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SAIA.2024.1},
  URN =		{urn:nbn:de:0030-drops-227410},
  doi =		{10.4230/OASIcs.SAIA.2024.1},
  annote =	{Keywords: ML model robustness, assessment, framework, methodological processes, tools}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.TQC.2023
LIPIcs, Volume 266, TQC 2023, Complete Volume

Authors: Omar Fawzi and Michael Walter

Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)

Abstract
LIPIcs, Volume 266, TQC 2023, Complete Volume
Cite as

18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 1-314, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Proceedings{fawzi_et_al:LIPIcs.TQC.2023,
  title =	{{LIPIcs, Volume 266, TQC 2023, Complete Volume}},
  booktitle =	{18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)},
  pages =	{1--314},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-283-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{266},
  editor =	{Fawzi, Omar and Walter, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023},
  URN =		{urn:nbn:de:0030-drops-183099},
  doi =		{10.4230/LIPIcs.TQC.2023},
  annote =	{Keywords: LIPIcs, Volume 266, TQC 2023, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.TQC.2023.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Omar Fawzi and Michael Walter

Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{fawzi_et_al:LIPIcs.TQC.2023.0,
  author =	{Fawzi, Omar and Walter, Michael},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)},
  pages =	{0:i--0:xii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-283-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{266},
  editor =	{Fawzi, Omar and Walter, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.0},
  URN =		{urn:nbn:de:0030-drops-183102},
  doi =		{10.4230/LIPIcs.TQC.2023.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.TQC.2023.1
Approximate Degree Lower Bounds for Oracle Identification Problems

Authors: Mark Bun and Nadezhda Voronova

Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)

Abstract
The approximate degree of a Boolean function is the minimum degree of real polynomial that approximates it pointwise. For any Boolean function, its approximate degree serves as a lower bound on its quantum query complexity, and generically lifts to a quantum communication lower bound for a related function. We introduce a framework for proving approximate degree lower bounds for certain oracle identification problems, where the goal is to recover a hidden binary string x ∈ {0, 1}ⁿ given possibly non-standard oracle access to it. Our lower bounds apply to decision versions of these problems, where the goal is to compute the parity of x. We apply our framework to the ordered search and hidden string problems, proving nearly tight approximate degree lower bounds of Ω(n/log² n) for each. These lower bounds generalize to the weakly unbounded error setting, giving a new quantum query lower bound for the hidden string problem in this regime. Our lower bounds are driven by randomized communication upper bounds for the greater-than and equality functions.
Cite as

Mark Bun and Nadezhda Voronova. Approximate Degree Lower Bounds for Oracle Identification Problems. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 1:1-1:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bun_et_al:LIPIcs.TQC.2023.1,
  author =	{Bun, Mark and Voronova, Nadezhda},
  title =	{{Approximate Degree Lower Bounds for Oracle Identification Problems}},
  booktitle =	{18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)},
  pages =	{1:1--1:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-283-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{266},
  editor =	{Fawzi, Omar and Walter, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.1},
  URN =		{urn:nbn:de:0030-drops-183113},
  doi =		{10.4230/LIPIcs.TQC.2023.1},
  annote =	{Keywords: Approximate degree, quantum query complexity, communication complexity, ordered search, polynomial approximations, polynomial method}
}
Document
DOI: 10.4230/LIPIcs.TQC.2023.2
On the Necessity of Collapsing for Post-Quantum and Quantum Commitments

Authors: Marcel Dall'Agnol and Nicholas Spooner

Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)

Abstract
Collapse binding and collapsing were proposed by Unruh (Eurocrypt '16) as post-quantum strengthenings of computational binding and collision resistance, respectively. These notions have been very successful in facilitating the "lifting" of classical security proofs to the quantum setting. A basic and natural question remains unanswered, however: are they the weakest notions that suffice for such lifting? In this work we answer this question in the affirmative by giving a classical commit-and-open protocol which is post-quantum secure if and only if the commitment scheme (resp. hash function) used is collapse binding (resp. collapsing). We also generalise the definition of collapse binding to quantum commitment schemes, and prove that the equivalence carries over when the sender in this commit-and-open protocol communicates quantum information. As a consequence, we establish that a variety of "weak" binding notions (sum binding, CDMS binding and unequivocality) are in fact equivalent to collapse binding, both for post-quantum and quantum commitments. Finally, we prove a "win-win" result, showing that a post-quantum computationally binding commitment scheme that is not collapse binding can be used to build an equivocal commitment scheme (which can, in turn, be used to build one-shot signatures and other useful quantum primitives). This strengthens a result due to Zhandry (Eurocrypt '19) showing that the same object yields quantum lightning.
Cite as

Marcel Dall'Agnol and Nicholas Spooner. On the Necessity of Collapsing for Post-Quantum and Quantum Commitments. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dallagnol_et_al:LIPIcs.TQC.2023.2,
  author =	{Dall'Agnol, Marcel and Spooner, Nicholas},
  title =	{{On the Necessity of Collapsing for Post-Quantum and Quantum Commitments}},
  booktitle =	{18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)},
  pages =	{2:1--2:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-283-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{266},
  editor =	{Fawzi, Omar and Walter, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.2},
  URN =		{urn:nbn:de:0030-drops-183127},
  doi =		{10.4230/LIPIcs.TQC.2023.2},
  annote =	{Keywords: Quantum cryptography, Commitment schemes, Hash functions, Quantum rewinding}
}
Document
DOI: 10.4230/LIPIcs.TQC.2023.3
Optimal Algorithms for Learning Quantum Phase States

Authors: Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder

Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)

Abstract
We analyze the complexity of learning n-qubit quantum phase states. A degree-d phase state is defined as a superposition of all 2ⁿ basis vectors x with amplitudes proportional to (-1)^{f(x)}, where f is a degree-d Boolean polynomial over n variables. We show that the sample complexity of learning an unknown degree-d phase state is Θ(n^d) if we allow separable measurements and Θ(n^{d-1}) if we allow entangled measurements. Our learning algorithm based on separable measurements has runtime poly(n) (for constant d) and is well-suited for near-term demonstrations as it requires only single-qubit measurements in the Pauli X and Z bases. We show similar bounds on the sample complexity for learning generalized phase states with complex-valued amplitudes. We further consider learning phase states when f has sparsity-s, degree-d in its 𝔽₂ representation (with sample complexity O(2^d sn)), f has Fourier-degree-t (with sample complexity O(2^{2t})), and learning quadratic phase states with ε-global depolarizing noise (with sample complexity O(n^{1+ε})). These learning algorithms give us a procedure to learn the diagonal unitaries of the Clifford hierarchy and IQP circuits.
Cite as

Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder. Optimal Algorithms for Learning Quantum Phase States. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 3:1-3:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.TQC.2023.3,
  author =	{Arunachalam, Srinivasan and Bravyi, Sergey and Dutt, Arkopal and Yoder, Theodore J.},
  title =	{{Optimal Algorithms for Learning Quantum Phase States}},
  booktitle =	{18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)},
  pages =	{3:1--3:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-283-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{266},
  editor =	{Fawzi, Omar and Walter, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.3},
  URN =		{urn:nbn:de:0030-drops-183139},
  doi =		{10.4230/LIPIcs.TQC.2023.3},
  annote =	{Keywords: Tomography, binary phase states, generalized phase states, IQP circuits}
}
Document
DOI: 10.4230/LIPIcs.TQC.2023.4
Computational Quantum Secret Sharing

Authors: Alper Çakan, Vipul Goyal, Chen-Da Liu-Zhang, and João Ribeiro

Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)

Abstract
Quantum secret sharing (QSS) allows a dealer to distribute a secret quantum state among a set of parties in such a way that certain authorized subsets can reconstruct the secret, while unauthorized subsets obtain no information about it. Previous works on QSS for general access structures focused solely on the existence of perfectly secure schemes, and the share size of the known schemes is necessarily exponential even in cases where the access structure is computed by polynomial size monotone circuits. This stands in stark contrast to the classical setting, where polynomial-time computationally-secure secret sharing schemes have been long known for all access structures computed by polynomial-size monotone circuits under standard hardness assumptions, and one can even obtain shares which are much shorter than the secret (which is impossible with perfect security). While QSS was introduced over twenty years ago, previous works only considered information-theoretic privacy. In this work, we initiate the study of computationally-secure QSS and show that computational assumptions help significantly in building QSS schemes, just as in the classical case. We present a simple compiler and use it to obtain a large variety results: We construct polynomial-time computationally-secure QSS schemes under standard hardness assumptions for a rich class of access structures. This includes many access structures for which previous results in QSS necessarily required exponential share size. In fact, we can go even further: We construct QSS schemes for which the size of the quantum shares is significantly smaller than the size of the secret. As in the classical setting, this is impossible with perfect security. We also apply our compiler to obtain results beyond computational QSS. In the information-theoretic setting, we improve the share size of perfect QSS schemes for a large class of n-party access structures to 1.5^{n+o(n)}, improving upon best known schemes and matching the best known result for general access structures in the classical setting. Finally, among other things, we study the class of access structures which can be efficiently implemented when the quantum secret sharing scheme has access to a given number of copies of the secret, including all such functions in 𝖯 and NP.
Cite as

Alper Çakan, Vipul Goyal, Chen-Da Liu-Zhang, and João Ribeiro. Computational Quantum Secret Sharing. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 4:1-4:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cakan_et_al:LIPIcs.TQC.2023.4,
  author =	{\c{C}akan, Alper and Goyal, Vipul and Liu-Zhang, Chen-Da and Ribeiro, Jo\~{a}o},
  title =	{{Computational Quantum Secret Sharing}},
  booktitle =	{18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)},
  pages =	{4:1--4:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-283-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{266},
  editor =	{Fawzi, Omar and Walter, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.4},
  URN =		{urn:nbn:de:0030-drops-183144},
  doi =		{10.4230/LIPIcs.TQC.2023.4},
  annote =	{Keywords: Quantum secret sharing, quantum cryptography}
}
  • Refine by Type
  • 31 Document/PDF
  • 8 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 4 2026
  • 4 2025
  • 18 2023
  • 2 2022
  • 3 2021
  • Show More...

  • Refine by Author
  • 8 Fawzi, Omar
  • 2 Berta, Mario
  • 2 Bostanci, John
  • 2 Fefferman, Bill
  • 2 Walter, Michael
  • Show More...

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

  • Refine by Classification
  • 11 Theory of computation → Quantum computation theory
  • 10 Theory of computation → Quantum complexity theory
  • 5 Theory of computation → Quantum information theory
  • 5 Theory of computation → Quantum query complexity
  • 3 Hardware → Quantum communication and cryptography
  • Show More...

  • Refine by Keyword
  • 2 communication complexity
  • 2 quantum cryptography
  • 2 quantum search
  • 1 Algorithm design and analysis
  • 1 Approximate degree
  • 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