2 Search Results for "Jordan, Alexander"

Document
DOI: 10.4230/LIPIcs.ITCS.2022.68
A Lower Bound on the Space Overhead of Fault-Tolerant Quantum Computation

Authors: Omar Fawzi, Alexander Müller-Hermes, and Ala Shayeghi

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation stating that arbitrarily long quantum computations can be performed with a polylogarithmic overhead provided the noise level is below a constant level. A recent work by Fawzi, Grospellier and Leverrier (FOCS 2018) building on a result by Gottesman (QIC 2013) has shown that the space overhead can be asymptotically reduced to a constant independent of the circuit provided we only consider circuits with a length bounded by a polynomial in the width. In this work, using a minimal model for quantum fault tolerance, we establish a general lower bound on the space overhead required to achieve fault tolerance. For any non-unitary qubit channel 𝒩 and any quantum fault tolerance schemes against i.i.d. noise modeled by 𝒩, we prove a lower bound of max{Q(𝒩)^{-1}n,α_𝒩 log T} on the number of physical qubits, for circuits of length T and width n. Here, Q(𝒩) denotes the quantum capacity of 𝒩 and α_𝒩 > 0 is a constant only depending on the channel 𝒩. In our model, we allow for qubits to be replaced by fresh ones during the execution of the circuit and in the case of unital noise, we allow classical computation to be free and perfect. This improves upon results that assumed classical computations to be also affected by noise, and that sometimes did not allow for fresh qubits to be added. Along the way, we prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude damping noise resolving a conjecture by Ben-Or, Gottesman and Hassidim (2013).
Cite as

Omar Fawzi, Alexander Müller-Hermes, and Ala Shayeghi. A Lower Bound on the Space Overhead of Fault-Tolerant Quantum Computation. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 68:1-68:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fawzi_et_al:LIPIcs.ITCS.2022.68,
  author =	{Fawzi, Omar and M\"{u}ller-Hermes, Alexander and Shayeghi, Ala},
  title =	{{A Lower Bound on the Space Overhead of Fault-Tolerant Quantum Computation}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{68:1--68:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.68},
  URN =		{urn:nbn:de:0030-drops-156649},
  doi =		{10.4230/LIPIcs.ITCS.2022.68},
  annote =	{Keywords: Fault-tolerant quantum computation, quantum error correction}
}
Document
DOI: 10.4230/OASIcs.WCET.2014.83
Lazy Spilling for a Time-Predictable Stack Cache: Implementation and Analysis

Authors: Sahar Abbaspour, Alexander Jordan, and Florian Brandner

Published in: OASIcs, Volume 39, 14th International Workshop on Worst-Case Execution Time Analysis (2014)

Abstract
The growing complexity of modern computer architectures increasingly complicates the prediction of the run-time behavior of software. For real-time systems, where a safe estimation of the program's worst-case execution time is needed, time-predictable computer architectures promise to resolve this problem. A stack cache, for instance, allows the compiler to efficiently cache a program's stack, while static analysis of its behavior remains easy. Likewise, its implementation requires little hardware overhead. This work introduces an optimization of the standard stack cache to avoid redundant spilling of the cache content to main memory, if the content was not modified in the meantime. At first sight, this appears to be an average-case optimization. Indeed, measurements show that the number of cache blocks spilled is reduced to about 17% and 30% in the mean, depending on the stack cache size. Furthermore, we show that lazy spilling can be analyzed with little extra effort, which benefits the worst-case spilling behavior that is relevant for a real-time system.
Cite as

Sahar Abbaspour, Alexander Jordan, and Florian Brandner. Lazy Spilling for a Time-Predictable Stack Cache: Implementation and Analysis. In 14th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 39, pp. 83-92, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{abbaspour_et_al:OASIcs.WCET.2014.83,
  author =	{Abbaspour, Sahar and Jordan, Alexander and Brandner, Florian},
  title =	{{Lazy Spilling for a Time-Predictable Stack Cache: Implementation and Analysis}},
  booktitle =	{14th International Workshop on Worst-Case Execution Time Analysis},
  pages =	{83--92},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-69-9},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{39},
  editor =	{Falk, Heiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2014.83},
  URN =		{urn:nbn:de:0030-drops-46073},
  doi =		{10.4230/OASIcs.WCET.2014.83},
  annote =	{Keywords: Lazy Spilling, Stack Cache, Real-Time Systems, Program Analysis}
}
  • Refine by Author
  • 1 Abbaspour, Sahar
  • 1 Brandner, Florian
  • 1 Fawzi, Omar
  • 1 Jordan, Alexander
  • 1 Müller-Hermes, Alexander
  • Show More...

  • Refine by Classification
  • 1 Hardware → Quantum error correction and fault tolerance
  • 1 Theory of computation → Quantum computation theory

  • Refine by Keyword
  • 1 Fault-tolerant quantum computation
  • 1 Lazy Spilling
  • 1 Program Analysis
  • 1 Real-Time Systems
  • 1 Stack Cache
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2014
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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