DROPS

Volume

LIPIcs, Volume 197

16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)

TQC 2021, July 5-8, 2021, Virtual Conference

Editors: Min-Hsiu Hsieh

Document

DOI: 10.4230/LIPIcs.ISAAC.2023.50

On Min-Max Graph Balancing with Strict Negative Correlation Constraints

Authors: Ting-Yu Kuo, Yu-Han Chen, Andrea Frosini, Sun-Yuan Hsieh, Shi-Chun Tsai, and Mong-Jen Kao

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract

We consider the min-max graph balancing problem with strict negative correlation (SNC) constraints. The graph balancing problem arises as an equivalent formulation of the classic unrelated machine scheduling problem, where we are given a hypergraph G = (V,E) with vertex-dependent edge weight function p: E×V ↦ ℤ^{≥0} that represents the processing time of the edges (jobs). The SNC constraints, which are given as edge subsets C_1,C_2,…,C_k, require that the edges in the same subset cannot be assigned to the same vertex at the same time. Under these constraints, the goal is to compute an edge orientation (assignment) that minimizes the maximum workload of the vertices. In this paper, we conduct a general study on the approximability of this problem. First, we show that, in the presence of SNC constraints, the case with max_{e ∈ E} |e| = max_i |C_i| = 2 is the only case for which approximation solutions can be obtained. Further generalization on either direction, e.g., max_{e ∈ E} |e| or max_i |C_i|, will directly make computing a feasible solution an NP-complete problem to solve. Then, we present a 2-approximation algorithm for the case with max_{e ∈ E} |e| = max_i |C_i| = 2, based on a set of structural simplifications and a tailored assignment LP for this problem. We note that our approach is general and can be applied to similar settings, e.g., scheduling with SNC constraints to minimize the weighted completion time, to obtain similar approximation guarantees. Further cases are discussed to describe the landscape of the approximability of this prbolem. For the case with |V| ≤ 2, which is already known to be NP-hard, we present a fully-polynomial time approximation scheme (FPTAS). On the other hand, we show that the problem is at least as hard as vertex cover to approximate when |V| ≥ 3.

Cite as

Ting-Yu Kuo, Yu-Han Chen, Andrea Frosini, Sun-Yuan Hsieh, Shi-Chun Tsai, and Mong-Jen Kao. On Min-Max Graph Balancing with Strict Negative Correlation Constraints. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 50:1-50:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kuo_et_al:LIPIcs.ISAAC.2023.50,
  author =	{Kuo, Ting-Yu and Chen, Yu-Han and Frosini, Andrea and Hsieh, Sun-Yuan and Tsai, Shi-Chun and Kao, Mong-Jen},
  title =	{{On Min-Max Graph Balancing with Strict Negative Correlation Constraints}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{50:1--50:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.50},
  URN =		{urn:nbn:de:0030-drops-193524},
  doi =		{10.4230/LIPIcs.ISAAC.2023.50},
  annote =	{Keywords: Unrelated Scheduling, Graph Balancing, Strict Correlation Constraints}
}

Document

DOI: 10.4230/LIPIcs.ESA.2023.64

Improved Quantum Boosting

Authors: Adam Izdebski and Ronald de Wolf

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract

Boosting is a general method to convert a weak learner (which generates hypotheses that are just slightly better than random) into a strong learner (which generates hypotheses that are much better than random). Recently, Arunachalam and Maity [Srinivasan Arunachalam and Reevu Maity, 2020] gave the first quantum improvement for boosting, by combining Freund and Schapire’s AdaBoost algorithm with a quantum algorithm for approximate counting. Their booster is faster than classical boosting as a function of the VC-dimension of the weak learner’s hypothesis class, but worse as a function of the quality of the weak learner. In this paper we give a substantially faster and simpler quantum boosting algorithm, based on Servedio’s SmoothBoost algorithm [Servedio, 2003].

Cite as

Adam Izdebski and Ronald de Wolf. Improved Quantum Boosting. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 64:1-64:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{izdebski_et_al:LIPIcs.ESA.2023.64,
  author =	{Izdebski, Adam and de Wolf, Ronald},
  title =	{{Improved Quantum Boosting}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{64:1--64:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.64},
  URN =		{urn:nbn:de:0030-drops-187178},
  doi =		{10.4230/LIPIcs.ESA.2023.64},
  annote =	{Keywords: Learning theory, Boosting algorithms, Quantum computing}
}

Document

DOI: 10.4230/LIPIcs.CCC.2023.33

On the Impossibility of General Parallel Fast-Forwarding of Hamiltonian Simulation

Authors: Nai-Hui Chia, Kai-Min Chung, Yao-Ching Hsieh, Han-Hsuan Lin, Yao-Ting Lin, and Yu-Ching Shen

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract

Hamiltonian simulation is one of the most important problems in the field of quantum computing. There have been extended efforts on designing algorithms for faster simulation, and the evolution time T for the simulation greatly affect algorithm runtime as expected. While there are some specific types of Hamiltonians that can be fast-forwarded, i.e., simulated within time o(T), for some large classes of Hamiltonians (e.g., all local/sparse Hamiltonians), existing simulation algorithms require running time at least linear in the evolution time T. On the other hand, while there exist lower bounds of Ω(T) circuit size for some large classes of Hamiltonian, these lower bounds do not rule out the possibilities of Hamiltonian simulation with large but "low-depth" circuits by running things in parallel. As a result, physical systems with system size scaling with T can potentially do a fast-forwarding simulation. Therefore, it is intriguing whether we can achieve fast Hamiltonian simulation with the power of parallelism. In this work, we give a negative result for the above open problem in various settings. In the oracle model, we prove that there are time-independent sparse Hamiltonians that cannot be simulated via an oracle circuit of depth o(T). In the plain model, relying on the random oracle heuristic, we show that there exist time-independent local Hamiltonians and time-dependent geometrically local Hamiltonians on n qubits that cannot be simulated via an oracle circuit of depth o(T/n^c), where the Hamiltonians act on n qubits, and c is a constant. Lastly, we generalize the above results and show that any simulators that are geometrically local Hamiltonians cannot do the simulation much faster than parallel quantum algorithms.

Cite as

Nai-Hui Chia, Kai-Min Chung, Yao-Ching Hsieh, Han-Hsuan Lin, Yao-Ting Lin, and Yu-Ching Shen. On the Impossibility of General Parallel Fast-Forwarding of Hamiltonian Simulation. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 33:1-33:45, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chia_et_al:LIPIcs.CCC.2023.33,
  author =	{Chia, Nai-Hui and Chung, Kai-Min and Hsieh, Yao-Ching and Lin, Han-Hsuan and Lin, Yao-Ting and Shen, Yu-Ching},
  title =	{{On the Impossibility of General Parallel Fast-Forwarding of Hamiltonian Simulation}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{33:1--33:45},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.33},
  URN =		{urn:nbn:de:0030-drops-183038},
  doi =		{10.4230/LIPIcs.CCC.2023.33},
  annote =	{Keywords: Hamiltonian simulation, Depth lower bound, Parallel query lower bound}
}

Document

Complete Volume

DOI: 10.4230/LIPIcs.TQC.2021

LIPIcs, Volume 197, TQC 2021, Complete Volume

Authors: Min-Hsiu Hsieh

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

Abstract

LIPIcs, Volume 197, TQC 2021, Complete Volume

Cite as

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

Copy BibTex To Clipboard

@Proceedings{hsieh:LIPIcs.TQC.2021,
  title =	{{LIPIcs, Volume 197, TQC 2021, Complete Volume}},
  booktitle =	{16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
  pages =	{1--178},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2021},
  URN =		{urn:nbn:de:0030-drops-139940},
  doi =		{10.4230/LIPIcs.TQC.2021},
  annote =	{Keywords: LIPIcs, Volume 197, TQC 2021, Complete Volume}
}

Document

Front Matter

DOI: 10.4230/LIPIcs.TQC.2021.0

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Min-Hsiu Hsieh

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

Abstract

Front Matter, Table of Contents, Preface, Conference Organization

Cite as

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

Copy BibTex To Clipboard

@InProceedings{hsieh:LIPIcs.TQC.2021.0,
  author =	{Hsieh, Min-Hsiu},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
  pages =	{0:i--0:xii},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2021.0},
  URN =		{urn:nbn:de:0030-drops-139958},
  doi =		{10.4230/LIPIcs.TQC.2021.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}

Document

DOI: 10.4230/LIPIcs.TQC.2021.1

Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs

Authors: Yassine Hamoudi and Frédéric Magniez

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

Abstract

We study the problem of finding K collision pairs in a random function f : [N] → [N] by using a quantum computer. We prove that the number of queries to the function in the quantum random oracle model must increase significantly when the size of the available memory is limited. Namely, we demonstrate that any algorithm using S qubits of memory must perform a number T of queries that satisfies the tradeoff T³ S ≥ Ω(K³N). Classically, the same question has only been settled recently by Dinur [Dinur, 2020], who showed that the Parallel Collision Search algorithm of van Oorschot and Wiener [Oorschot and Wiener, 1999] achieves the optimal time-space tradeoff of T² S = Θ(K² N). Our result limits the extent to which quantum computing may decrease this tradeoff. Our method is based on a novel application of Zhandry’s recording query technique [Zhandry, 2019] for proving lower bounds in the exponentially small success probability regime. As a second application, we give a simpler proof of the time-space tradeoff T² S ≥ Ω(N³) for sorting N numbers on a quantum computer, which was first obtained by Klauck, Špalek and de Wolf [Klauck et al., 2007].

Cite as

Yassine Hamoudi and Frédéric Magniez. Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 1:1-1:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{hamoudi_et_al:LIPIcs.TQC.2021.1,
  author =	{Hamoudi, Yassine and Magniez, Fr\'{e}d\'{e}ric},
  title =	{{Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs}},
  booktitle =	{16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
  pages =	{1:1--1:21},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2021.1},
  URN =		{urn:nbn:de:0030-drops-139961},
  doi =		{10.4230/LIPIcs.TQC.2021.1},
  annote =	{Keywords: Quantum computing, query complexity, lower bound, time-space tradeoff}
}

Document

DOI: 10.4230/LIPIcs.TQC.2021.2

Quantum Pseudorandomness and Classical Complexity

Authors: William Kretschmer

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

Abstract

We construct a quantum oracle relative to which BQP = QMA but cryptographic pseudorandom quantum states and pseudorandom unitary transformations exist, a counterintuitive result in light of the fact that pseudorandom states can be "broken" by quantum Merlin-Arthur adversaries. We explain how this nuance arises as the result of a distinction between algorithms that operate on quantum and classical inputs. On the other hand, we show that some computational complexity assumption is needed to construct pseudorandom states, by proving that pseudorandom states do not exist if BQP = PP. We discuss implications of these results for cryptography, complexity theory, and quantum tomography.

Cite as

William Kretschmer. Quantum Pseudorandomness and Classical Complexity. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kretschmer:LIPIcs.TQC.2021.2,
  author =	{Kretschmer, William},
  title =	{{Quantum Pseudorandomness and Classical Complexity}},
  booktitle =	{16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
  pages =	{2:1--2:20},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2021.2},
  URN =		{urn:nbn:de:0030-drops-139975},
  doi =		{10.4230/LIPIcs.TQC.2021.2},
  annote =	{Keywords: pseudorandom quantum states, quantum Merlin-Arthur}
}

Document

DOI: 10.4230/LIPIcs.TQC.2021.3

Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problem

Authors: Kai-Min Chung and Han-Hsuan Lin

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

Abstract

The probably approximately correct (PAC) model [Leslie G. Valiant, 1984] is a well studied model in classical learning theory. Here, we generalize the PAC model from concepts of Boolean functions to quantum channels, introducing PAC model for learning quantum channels, and give two sample efficient algorithms that are analogous to the classical "Occam’s razor" result [Blumer et al., 1987]. The classical Occam’s razor algorithm is done trivially by excluding any concepts not compatible with the input-output pairs one gets, but such an approach is not immediately possible with a concept class of quantum channels, because the outputs are unknown quantum states from the quantum channel. To study the quantum state learning problem associated with PAC learning quantum channels, we focus on the special case where the channels all have constant output. In this special case, learning the channels reduce to a problem of learning quantum states that is similar to the well known quantum state discrimination problem [Joonwoo Bae and Leong-Chuan Kwek, 2017], but with the extra twist that we allow ε-trace-distance-error in the output. We call this problem Approximate State Discrimination, which we believe is a natural problem that is of independent interest. We give two algorithms for learning quantum channels in PAC model. The first algorithm has sample complexity O((log|C| + log(1/ δ))/(ε²)), but only works when the outputs are pure states, where C is the concept class, ε is the error of the output, and δ is the probability of failure of the algorithm. The second algorithm has sample complexity O((log³|C|(log|C|+log(1/ δ)))/(ε²)), and work for mixed state outputs. Some implications of our results are that we can PAC-learn a polynomial sized quantum circuit in polynomial samples, and approximate state discrimination can be solved in polynomial samples even when the size of the input set is exponential in the number of qubits, exponentially better than a naive state tomography.

Cite as

Kai-Min Chung and Han-Hsuan Lin. Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problem. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 3:1-3:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{chung_et_al:LIPIcs.TQC.2021.3,
  author =	{Chung, Kai-Min and Lin, Han-Hsuan},
  title =	{{Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problem}},
  booktitle =	{16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
  pages =	{3:1--3:22},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2021.3},
  URN =		{urn:nbn:de:0030-drops-139984},
  doi =		{10.4230/LIPIcs.TQC.2021.3},
  annote =	{Keywords: PAC learning, Quantum PAC learning, Sample Complexity, Approximate State Discrimination, Quantum information}
}

Document

DOI: 10.4230/LIPIcs.TQC.2021.4

StoqMA Meets Distribution Testing

Authors: Yupan Liu

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

Abstract

StoqMA captures the computational hardness of approximating the ground energy of local Hamiltonians that do not suffer the so-called sign problem. We provide a novel connection between StoqMA and distribution testing via reversible circuits. First, we prove that easy-witness StoqMA (viz. eStoqMA, a sub-class of StoqMA) is contained in MA. Easy witness is a generalization of a subset state such that the associated set’s membership can be efficiently verifiable, and all non-zero coordinates are not necessarily uniform. This sub-class eStoqMA contains StoqMA with perfect completeness (StoqMA₁), which further signifies a simplified proof for StoqMA₁ ⊆ MA [Bravyi et al., 2006; Bravyi and Terhal, 2010]. Second, by showing distinguishing reversible circuits with ancillary random bits is StoqMA-complete (as a comparison, distinguishing quantum circuits is QMA-complete [Janzing et al., 2005]), we construct soundness error reduction of StoqMA. Additionally, we show that both variants of StoqMA that without any ancillary random bit and with perfect soundness are contained in NP. Our results make a step towards collapsing the hierarchy MA ⊆ StoqMA ⊆ SBP [Bravyi et al., 2006], in which all classes are contained in AM and collapse to NP under derandomization assumptions.

Cite as

Yupan Liu. StoqMA Meets Distribution Testing. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{liu:LIPIcs.TQC.2021.4,
  author =	{Liu, Yupan},
  title =	{{StoqMA Meets Distribution Testing}},
  booktitle =	{16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
  pages =	{4:1--4:22},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2021.4},
  URN =		{urn:nbn:de:0030-drops-139995},
  doi =		{10.4230/LIPIcs.TQC.2021.4},
  annote =	{Keywords: StoqMA, distribution testing, error reduction, reversible circuits}
}

Document

DOI: 10.4230/LIPIcs.TQC.2021.5

Fault-Tolerant Syndrome Extraction and Cat State Preparation with Fewer Qubits

Authors: Prithviraj Prabhu and Ben W. Reichardt

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

Abstract

We reduce the extra qubits needed for two fault-tolerant quantum computing protocols: error correction, specifically syndrome bit measurement, and cat state preparation. For fault-tolerant syndrome extraction, we show an exponential reduction in qubit overhead over the previous best protocol. For a weight-w stabilizer, we demonstrate that stabilizer measurement tolerating one fault (distance-three) needs at most ⌈ log₂ w ⌉ + 1 ancillas. If qubits reset quickly, four ancillas suffice. We also study the preparation of cat states, simple yet versatile entangled states. We prove that the overhead needed for distance-three fault tolerance is only logarithmic in the cat state size. These results could be useful both for near-term experiments with a few qubits, and for the general study of the asymptotic resource requirements of syndrome measurement and state preparation. For 'a' measured flag bits, there are 2^a possible flag patterns that can identify faults. Hence our results come from solving a combinatorial problem: the construction of maximal-length paths in the a-dimensional hypercube, corresponding to maximal-weight stabilizers or maximal-weight cat states.

Cite as

Prithviraj Prabhu and Ben W. Reichardt. Fault-Tolerant Syndrome Extraction and Cat State Preparation with Fewer Qubits. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{prabhu_et_al:LIPIcs.TQC.2021.5,
  author =	{Prabhu, Prithviraj and Reichardt, Ben W.},
  title =	{{Fault-Tolerant Syndrome Extraction and Cat State Preparation with Fewer Qubits}},
  booktitle =	{16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
  pages =	{5:1--5:13},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2021.5},
  URN =		{urn:nbn:de:0030-drops-140001},
  doi =		{10.4230/LIPIcs.TQC.2021.5},
  annote =	{Keywords: Quantum error correction, fault tolerance, quantum state preparation, combinatorics}
}

Document

DOI: 10.4230/LIPIcs.TQC.2021.6

A Note About Claw Function with a Small Range

Authors: Andris Ambainis, Kaspars Balodis, and Jānis Iraids

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

Abstract

In the claw detection problem we are given two functions f:D → R and g:D → R (|D| = n, |R| = k), and we have to determine if there is exist x,y ∈ D such that f(x) = g(y). We show that the quantum query complexity of this problem is between Ω(n^{1/2}k^{1/6}) and O(n^{1/2+ε}k^{1/4}) when 2 ≤ k < n.

Cite as

Andris Ambainis, Kaspars Balodis, and Jānis Iraids. A Note About Claw Function with a Small Range. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 6:1-6:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ambainis_et_al:LIPIcs.TQC.2021.6,
  author =	{Ambainis, Andris and Balodis, Kaspars and Iraids, J\={a}nis},
  title =	{{A Note About Claw Function with a Small Range}},
  booktitle =	{16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
  pages =	{6:1--6:5},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2021.6},
  URN =		{urn:nbn:de:0030-drops-140013},
  doi =		{10.4230/LIPIcs.TQC.2021.6},
  annote =	{Keywords: collision, claw, quantum query complexity}
}

Document

DOI: 10.4230/LIPIcs.TQC.2021.7

Fast and Robust Quantum State Tomography from Few Basis Measurements

Authors: Daniel Stilck França, Fernando G.S L. Brandão, and Richard Kueng

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

Abstract

Quantum state tomography is a powerful but resource-intensive, general solution for numerous quantum information processing tasks. This motivates the design of robust tomography procedures that use relevant resources as sparingly as possible. Important cost factors include the number of state copies and measurement settings, as well as classical postprocessing time and memory. In this work, we present and analyze an online tomography algorithm designed to optimize all the aforementioned resources at the cost of a worse dependence on accuracy. The protocol is the first to give provably optimal performance in terms of rank and dimension for state copies, measurement settings and memory. Classical runtime is also reduced substantially and numerical experiments demonstrate a favorable comparison with other state-of-the-art techniques. Further improvements are possible by executing the algorithm on a quantum computer, giving a quantum speedup for quantum state tomography.

Cite as

Daniel Stilck França, Fernando G.S L. Brandão, and Richard Kueng. Fast and Robust Quantum State Tomography from Few Basis Measurements. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{franca_et_al:LIPIcs.TQC.2021.7,
  author =	{Fran\c{c}a, Daniel Stilck and Brand\~{a}o, Fernando G.S L. and Kueng, Richard},
  title =	{{Fast and Robust Quantum State Tomography from Few Basis Measurements}},
  booktitle =	{16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
  pages =	{7:1--7:13},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2021.7},
  URN =		{urn:nbn:de:0030-drops-140023},
  doi =		{10.4230/LIPIcs.TQC.2021.7},
  annote =	{Keywords: quantum tomography, low-rank tomography, Gibbs states, random measurements}
}

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-dev.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.2021.9

Quantum Probability Oracles & Multidimensional Amplitude Estimation

Authors: Joran van Apeldoorn

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

Abstract

We give a multidimensional version of amplitude estimation. Let p be an n-dimensional probability distribution which can be sampled from using a quantum circuit U_p. We show that all coordinates of p can be estimated up to error ε per coordinate using Õ(1/(ε)) applications of U_p and its inverse. This generalizes the normal amplitude estimation algorithm, which solves the problem for n = 2. Our results also imply a Õ(n/ε) query algorithm for 𝓁₁-norm (the total variation distance) estimation and a Õ(√n/ε) query algorithm for 𝓁₂-norm. We also show that these results are optimal up to logarithmic factors.

Cite as

Joran van Apeldoorn. Quantum Probability Oracles & Multidimensional Amplitude Estimation. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 9:1-9:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{vanapeldoorn:LIPIcs.TQC.2021.9,
  author =	{van Apeldoorn, Joran},
  title =	{{Quantum Probability Oracles \& Multidimensional Amplitude Estimation}},
  booktitle =	{16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
  pages =	{9:1--9:11},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2021.9},
  URN =		{urn:nbn:de:0030-drops-140046},
  doi =		{10.4230/LIPIcs.TQC.2021.9},
  annote =	{Keywords: quantum algorithms, amplitude estimation, monte carlo}
}

17 Search Results for "Hsieh, Min-Hsiu"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message