DROPS

Volume

LIPIcs, Volume 158

15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)

TQC 2020, June 9-12, 2020, Riga, Latvia

Editors: Steven T. Flammia

Volume

LIPIcs, Volume 27

9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)

TQC 2014, May 21-23, 2014, Singapore

Editors: Steven T. Flammia and Aram W. Harrow

Document

DOI: 10.4230/LIPIcs.ITCS.2026.10

On the Complexity of Unique Quantum Witnesses and Quantum Approximate Counting

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

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

Abstract

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

Cite as

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

Copy BibTex To Clipboard

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

Document

DOI: 10.4230/LIPIcs.ITCS.2026.109

Cloning Games, Black Holes and Cryptography

Authors: Alexander Poremba, Seyoon Ragavan, and Vinod Vaikuntanathan

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

Abstract

In this work, we introduce a new toolkit for analyzing cloning games, a notion that captures stronger and more quantitative versions of the celebrated quantum no-cloning theorem. This framework allows us to analyze a new cloning game based on binary phase states. Our results provide evidence that these games may be able to overcome important limitations of previous candidates based on BB84 states and subspace coset states: in a model where the adversaries are restricted to making a single oracle query, we show that the binary phase variant is t-copy secure when t = o(n/log n). Moreover, for constant t, we obtain the first optimal bounds of O(2^{-n}), asymptotically matching the value attained by a trivial adversarial strategy. We also show a worst-case to average-case reduction which allows us to show the same quantitative results for the new and natural notion of Haar cloning games. Our analytic toolkit, which we believe will find further applications, is based on binary subtypes and uses novel bounds on the operator norms of block-wise tensor products of matrices. To illustrate the effectiveness of these new techniques, we present two applications: first, in black-hole physics, where our asymptotically optimal bound offers quantitative insights into information scrambling in idealized models of black holes; and second, in unclonable cryptography, where we (a) construct succinct unclonable encryption schemes from the existence of pseudorandom unitaries, and (b) propose and provide evidence for the security of multi-copy unclonable encryption schemes.

Cite as

Alexander Poremba, Seyoon Ragavan, and Vinod Vaikuntanathan. Cloning Games, Black Holes and Cryptography. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 109:1-109:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{poremba_et_al:LIPIcs.ITCS.2026.109,
  author =	{Poremba, Alexander and Ragavan, Seyoon and Vaikuntanathan, Vinod},
  title =	{{Cloning Games, Black Holes and Cryptography}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{109:1--109:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.109},
  URN =		{urn:nbn:de:0030-drops-253961},
  doi =		{10.4230/LIPIcs.ITCS.2026.109},
  annote =	{Keywords: Unclonable cryptography, quantum pseudorandomness, black hole physics}
}

Document

DOI: 10.4230/LIPIcs.ESA.2025.4

Optimal Quantum Algorithm for Estimating Fidelity to a Pure State

Authors: Wang Fang and Qisheng Wang

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

Abstract

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

Cite as

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

Copy BibTex To Clipboard

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

Document

DOI: 10.4230/LIPIcs.WADS.2025.14

Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms

Authors: Susanna Caroppo, Giordano Da Lozzo, Giuseppe Di Battista, Michael T. Goodrich, and Martin Nöllenburg

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract

We introduce a quantum dynamic programming framework that allows us to directly extend to the quantum realm a large body of classical dynamic programming algorithms. The corresponding quantum dynamic programming algorithms retain the same space complexity as their classical counterpart, while achieving a computational speedup. For a combinatorial (search or optimization) problem P and an instance I of P, such a speedup can be expressed in terms of the average degree δ of the {dependency digraph} G_𝒫(I) of I, determined by a recursive formulation of P. The nodes of this graph are the subproblems of P induced by I and its arcs are directed from each subproblem to those on whose solution it relies. In particular, our framework allows us to solve the considered problems in Õ(|V(G_𝒫(I))| √δ) time. As an example, we obtain a quantum version of the Bellman-Ford algorithm for computing shortest paths from a single source vertex to all the other vertices in a weighted n-vertex digraph with m edges that runs in Õ(n√{nm}) time, which improves the best known classical upper bound when m ∈ Ω(n^{1.4}).

Cite as

Susanna Caroppo, Giordano Da Lozzo, Giuseppe Di Battista, Michael T. Goodrich, and Martin Nöllenburg. Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 14:1-14:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{caroppo_et_al:LIPIcs.WADS.2025.14,
  author =	{Caroppo, Susanna and Da Lozzo, Giordano and Di Battista, Giuseppe and Goodrich, Michael T. and N\"{o}llenburg, Martin},
  title =	{{Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{14:1--14:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.14},
  URN =		{urn:nbn:de:0030-drops-242454},
  doi =		{10.4230/LIPIcs.WADS.2025.14},
  annote =	{Keywords: Dynamic Programming, Quantum Algorithms, Quantum Random Access Memory}
}

Document

DOI: 10.4230/LIPIcs.CCC.2025.25

Quantum LDPC Codes of Almost Linear Distance via Iterated Homological Products

Authors: Louis Golowich and Venkatesan Guruswami

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

Abstract

The first linear-distance quantum LDPC codes were recently constructed by a line of breakthrough works (culminating in the result of Panteleev & Kalachev, 2021). All such constructions, even when allowing for almost-linear distance, are based on an operation called a balanced (or lifted) product, which is used in a one-shot manner to combine a pair of large classical codes possessing a group symmetry. We present a new construction of almost-linear distance quantum LDPC codes that is iterative in nature. Our construction is based on a more basic and widely used product, namely the homological product (i.e. the tensor product of chain complexes). Specifically, for every ε > 0, we obtain a family of [[N,N^{1-ε},N^{1-ε}]] (subsystem) quantum LDPC codes via repeated homological products of a constant-sized quantum locally testable code. Our key idea is to remove certain low-weight codewords using subsystem codes (while still maintaining constant stabilizer weight), in order to circumvent a particular obstruction that limited the distance of many prior homological product code constructions to at most Õ(√N).

Cite as

Louis Golowich and Venkatesan Guruswami. Quantum LDPC Codes of Almost Linear Distance via Iterated Homological Products. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 25:1-25:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{golowich_et_al:LIPIcs.CCC.2025.25,
  author =	{Golowich, Louis and Guruswami, Venkatesan},
  title =	{{Quantum LDPC Codes of Almost Linear Distance via Iterated Homological Products}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{25:1--25:11},
  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.25},
  URN =		{urn:nbn:de:0030-drops-237196},
  doi =		{10.4230/LIPIcs.CCC.2025.25},
  annote =	{Keywords: Quantum Error Correction, Quantum LDPC Code, Homological Product, Iterative Construction}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2025.7

Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography

Authors: Prabhanjan Ananth, Fatih Kaleoglu, and Henry Yuen

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

Abstract

We study a novel question about nonlocal quantum state discrimination: how well can non-communicating - but entangled - players distinguish between different distributions over quantum states? We call this task simultaneous state indistinguishability. Our main technical result is to show that the players cannot distinguish between each player receiving independently-chosen Haar random states versus all players receiving the same Haar random state. We show that this question has implications to unclonable cryptography, which leverages the no-cloning principle to build cryptographic primitives that are classically impossible to achieve. Understanding the feasibility of unclonable encryption, one of the key unclonable primitives, satisfying indistinguishability security in the plain model has been a major open question in the area. So far, the existing constructions of unclonable encryption are either in the quantum random oracle model or are based on new conjectures. We leverage our main result to present the first construction of unclonable encryption satisfying indistinguishability security, with quantum decryption keys, in the plain model. We also show other implications to single-decryptor encryption and leakage-resilient secret sharing. These applications present evidence that simultaneous Haar indistinguishability could be useful in quantum cryptography.

Cite as

Prabhanjan Ananth, Fatih Kaleoglu, and Henry Yuen. Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ananth_et_al:LIPIcs.ITCS.2025.7,
  author =	{Ananth, Prabhanjan and Kaleoglu, Fatih and Yuen, Henry},
  title =	{{Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{7:1--7:23},
  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.7},
  URN =		{urn:nbn:de:0030-drops-226352},
  doi =		{10.4230/LIPIcs.ITCS.2025.7},
  annote =	{Keywords: Quantum, Haar, unclonable encryption}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2025.96

Formulations and Constructions of Remote State Preparation with Verifiability, with Applications

Authors: Jiayu Zhang

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

Abstract

Remote state preparation with verifiability (RSPV) is an important quantum cryptographic primitive [Alexandru Gheorghiu and Thomas Vidick, 2019; Jiayu Zhang, 2022]. In this primitive, a client would like to prepare a quantum state (sampled or chosen from a state family) on the server side, such that ideally the client knows its full description, while the server holds and only holds the state itself. In this work we make several contributions on its formulations, constructions and applications. In more detail: - We first work on the definitions and abstract properties of the RSPV problem. We select and compare different variants of definitions [Bennett et al., 2001; Alexandru Gheorghiu and Thomas Vidick, 2019; Jiayu Zhang, 2022; Alexandru Gheorghiu et al., 2022], and study their basic properties (like composability and amplification). - We also study a closely related question of how to certify the server’s operations (instead of solely the states). We introduce a new notion named remote operator application with verifiability (ROAV). We compare this notion with related existing definitions [Summers and Werner, 1987; Dominic Mayers and Andrew Chi-Chih Yao, 2004; Zhengfeng Ji et al., 2021; Tony Metger and Thomas Vidick, 2021; Anand Natarajan and Tina Zhang, 2023], study its abstract properties and leave its concrete constructions for further works. - Building on the abstract properties and existing results [Zvika Brakerski et al., 2023], we construct a series of new RSPV protocols. Our constructions not only simplify existing results [Alexandru Gheorghiu and Thomas Vidick, 2019] but also cover new state families, for example, states in the form of 1/√2 (|0⟩ + |x_0⟩ + |1⟩ |x_1⟩). All these constructions rely only on the existence of weak NTCF [Zvika Brakerski et al., 2020; Navid Alamati et al., 2022], without additional requirements like the adaptive hardcore bit property [Zvika Brakerski et al., 2018; Navid Alamati et al., 2022]. - As a further application, we show that the classical verification of quantum computations (CVQC) problem [Dorit Aharonov et al., 2010; Urmila Mahadev, 2018] could be constructed from assumptions on group actions [Navid Alamati et al., 2020]. This is achieved by combining our results on RSPV with group-action-based instantiation of weak NTCF [Navid Alamati et al., 2022], and then with the quantum-gadget-assisted quantum verification protocol [Ferracin et al., 2018].

Cite as

Jiayu Zhang. Formulations and Constructions of Remote State Preparation with Verifiability, with Applications. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 96:1-96:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{zhang:LIPIcs.ITCS.2025.96,
  author =	{Zhang, Jiayu},
  title =	{{Formulations and Constructions of Remote State Preparation with Verifiability, with Applications}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{96:1--96:19},
  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.96},
  URN =		{urn:nbn:de:0030-drops-227245},
  doi =		{10.4230/LIPIcs.ITCS.2025.96},
  annote =	{Keywords: Quantum Cryptography, Remote State Preparation, Self-testing, Verification of Quantum Computations}
}

Document

DOI: 10.4230/LIPIcs.TQC.2022.4

Averaged Circuit Eigenvalue Sampling

Authors: Steven T. Flammia

Published in: LIPIcs, Volume 232, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)

Abstract

We introduce ACES, a method for scalable noise metrology of quantum circuits that stands for Averaged Circuit Eigenvalue Sampling. It simultaneously estimates the individual error rates of all the gates in collections of quantum circuits, and can even account for space and time correlations between these gates. ACES strictly generalizes randomized benchmarking (RB), interleaved RB, simultaneous RB, and several other related techniques. However, ACES provides much more information and provably works under strictly weaker assumptions than these techniques. Finally, ACES is extremely scalable: we demonstrate with numerical simulations that it simultaneously and precisely estimates all the Pauli error rates on every gate and measurement in a 100 qubit quantum device using fewer than 20 relatively shallow Clifford circuits and an experimentally feasible number of samples. By learning the detailed gate errors for large quantum devices, ACES opens new possibilities for error mitigation, bespoke quantum error correcting codes and decoders, customized compilers, and more.

Cite as

Steven T. Flammia. Averaged Circuit Eigenvalue Sampling. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 232, pp. 4:1-4:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{flammia:LIPIcs.TQC.2022.4,
  author =	{Flammia, Steven T.},
  title =	{{Averaged Circuit Eigenvalue Sampling}},
  booktitle =	{17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)},
  pages =	{4:1--4:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-237-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{232},
  editor =	{Le Gall, Fran\c{c}ois and Morimae, Tomoyuki},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2022.4},
  URN =		{urn:nbn:de:0030-drops-165114},
  doi =		{10.4230/LIPIcs.TQC.2022.4},
  annote =	{Keywords: Quantum noise estimation, quantum benchmarking, QCVV}
}

Document

DOI: 10.4230/LIPIcs.TQC.2021.8

Pauli Error Estimation via Population Recovery

Authors: Steven T. Flammia and Ryan O'Donnell

Published in: LIPIcs, Volume 197, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)

Abstract

Motivated by estimation of quantum noise models, we study the problem of learning a Pauli channel, or more generally the Pauli error rates of an arbitrary channel. By employing a novel reduction to the "Population Recovery" problem, we give an extremely simple algorithm that learns the Pauli error rates of an n-qubit channel to precision ε in 𝓁_∞ using just O(1/ε²) log(n/ε) applications of the channel. This is optimal up to the logarithmic factors. Our algorithm uses only unentangled state preparation and measurements, and the post-measurement classical runtime is just an O(1/ε) factor larger than the measurement data size. It is also impervious to a limited model of measurement noise where heralded measurement failures occur independently with probability ≤ 1/4. We then consider the case where the noise channel is close to the identity, meaning that the no-error outcome occurs with probability 1-η. In the regime of small η we extend our algorithm to achieve multiplicative precision 1 ± ε (i.e., additive precision εη) using just O(1/(ε²η)) log(n/ε) applications of the channel.

Cite as

Steven T. Flammia and Ryan O'Donnell. Pauli Error Estimation via Population Recovery. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{flammia_et_al:LIPIcs.TQC.2021.8,
  author =	{Flammia, Steven T. and O'Donnell, Ryan},
  title =	{{Pauli Error Estimation via Population Recovery}},
  booktitle =	{16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-198-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{197},
  editor =	{Hsieh, Min-Hsiu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2021.8},
  URN =		{urn:nbn:de:0030-drops-140034},
  doi =		{10.4230/LIPIcs.TQC.2021.8},
  annote =	{Keywords: Pauli channels, population recovery, Goldreich-Levin, sparse recovery, quantum channel tomography}
}

Document

DOI: 10.4230/LIPIcs.TQC.2020.12

A Device-Independent Protocol for XOR Oblivious Transfer

Authors: Srijita Kundu, Jamie Sikora, and Ernest Y.-Z. Tan

Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)

Abstract

Oblivious transfer is a cryptographic primitive where Alice has two bits and Bob wishes to learn some function of them. Ideally, Alice should not learn Bob’s desired function choice and Bob should not learn any more than logically implied by the function value. While decent quantum protocols for this task are known, many quickly become insecure if an adversary were to control the quantum devices used in the implementation of the protocol. Here we present how some existing protocols fail in this device-independent framework, and give a fully-device independent quantum protocol for XOR oblivious transfer which is provably more secure than any classical protocol.

Cite as

Srijita Kundu, Jamie Sikora, and Ernest Y.-Z. Tan. A Device-Independent Protocol for XOR Oblivious Transfer. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kundu_et_al:LIPIcs.TQC.2020.12,
  author =	{Kundu, Srijita and Sikora, Jamie and Tan, Ernest Y.-Z.},
  title =	{{A Device-Independent Protocol for XOR Oblivious Transfer}},
  booktitle =	{15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-146-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{158},
  editor =	{Flammia, Steven T.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.12},
  URN =		{urn:nbn:de:0030-drops-127579},
  doi =		{10.4230/LIPIcs.TQC.2020.12},
  annote =	{Keywords: Quantum cryptography, device independence, oblivious transfer, semidefinite programming, security analysis}
}

Document

Complete Volume

DOI: 10.4230/LIPIcs.TQC.2020

LIPIcs, Volume 158, TQC 2020, Complete Volume

Authors: Steven T. Flammia

Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)

Abstract

LIPIcs, Volume 158, TQC 2020, Complete Volume

Cite as

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

Copy BibTex To Clipboard

@Proceedings{flammia:LIPIcs.TQC.2020,
  title =	{{LIPIcs, Volume 158, TQC 2020, Complete Volume}},
  booktitle =	{15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)},
  pages =	{1--230},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-146-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{158},
  editor =	{Flammia, Steven T.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020},
  URN =		{urn:nbn:de:0030-drops-120583},
  doi =		{10.4230/LIPIcs.TQC.2020},
  annote =	{Keywords: LIPIcs, Volume 158, TQC 2020, Complete Volume}
}

Document

Front Matter

DOI: 10.4230/LIPIcs.TQC.2020.0

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Steven T. Flammia

Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)

Abstract

Front Matter, Table of Contents, Preface, Conference Organization

Cite as

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

Copy BibTex To Clipboard

@InProceedings{flammia:LIPIcs.TQC.2020.0,
  author =	{Flammia, Steven T.},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)},
  pages =	{0:i--0:x},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-146-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{158},
  editor =	{Flammia, Steven T.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.0},
  URN =		{urn:nbn:de:0030-drops-120598},
  doi =		{10.4230/LIPIcs.TQC.2020.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}

Document

DOI: 10.4230/LIPIcs.TQC.2020.1

Exponential Quantum Communication Reductions from Generalizations of the Boolean Hidden Matching Problem

Authors: João F. Doriguello and Ashley Montanaro

Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)

Abstract

In this work we revisit the Boolean Hidden Matching communication problem, which was the first communication problem in the one-way model to demonstrate an exponential classical-quantum communication separation. In this problem, Alice’s bits are matched into pairs according to a partition that Bob holds. These pairs are compressed using a Parity function and it is promised that the final bit-string is equal either to another bit-string Bob holds, or its complement. The problem is to decide which case is the correct one. Here we generalize the Boolean Hidden Matching problem by replacing the parity function with an arbitrary function f. Efficient communication protocols are presented depending on the sign-degree of f. If its sign-degree is less than or equal to 1, we show an efficient classical protocol. If its sign-degree is less than or equal to 2, we show an efficient quantum protocol. We then completely characterize the classical hardness of all symmetric functions f of sign-degree greater than or equal to 2, except for one family of specific cases. We also prove, via Fourier analysis, a classical lower bound for any function f whose pure high degree is greater than or equal to 2. Similarly, we prove, also via Fourier analysis, a quantum lower bound for any function f whose pure high degree is greater than or equal to 3. These results give a large family of new exponential classical-quantum communication separations.

Cite as

João F. Doriguello and Ashley Montanaro. Exponential Quantum Communication Reductions from Generalizations of the Boolean Hidden Matching Problem. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{doriguello_et_al:LIPIcs.TQC.2020.1,
  author =	{Doriguello, Jo\~{a}o F. and Montanaro, Ashley},
  title =	{{Exponential Quantum Communication Reductions from Generalizations of the Boolean Hidden Matching Problem}},
  booktitle =	{15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)},
  pages =	{1:1--1:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-146-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{158},
  editor =	{Flammia, Steven T.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.1},
  URN =		{urn:nbn:de:0030-drops-120601},
  doi =		{10.4230/LIPIcs.TQC.2020.1},
  annote =	{Keywords: Communication Complexity, Quantum Communication Complexity, Boolean Hidden Matching Problem}
}

45 Search Results for "Flammia, Steven T."

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message