---
OA_place: publisher
OA_type: hybrid
_id: '19499'
abstract:
- lang: eng
  text: Quantum hardware is inherently fragile and noisy. We find that the accuracy
    of traditional quantum error correction algorithms can be improved depending on
    the hardware. Given different hardware specifications, we automatically synthesize
    hardware-optimal algorithms for parity correction, qubit resetting, and GHZ (Greenberger–Horne–Zeilinger)
    state preparation. Using stochastic techniques from computer science, our method
    presents a computational tool to compute exact accuracy guarantees and synthesize
    optimal algorithms that are often different from traditional ones. We also show
    that improvements can be gained with respect to the Qiskit transpiler as we compute
    the hardware-optimal qubit mapping for the GHZ state-preparation problem.
acknowledgement: We thank the reviewers. In particular, they inspired us to analyze
  the reset and state-preparation problems, to compute optimal qubit mappings, and
  to apply our method to a quantum error correction scheme that includes both bitflip
  and phaseflip corrections. We also thank Raimundo Saona and Marek Chalupa for their
  time spent in insightful discussions. This research was partially supported by the
  European Research Council CoG 863818 (ForM-SMArt) grant.
article_number: e2419273122
article_processing_charge: Yes (in subscription journal)
article_type: original
author:
- first_name: Stefanie
  full_name: Muroya Lei, Stefanie
  id: a376de31-8972-11ed-ae7b-d0251c13c8ff
  last_name: Muroya Lei
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000-0002-2985-7724
citation:
  ama: Muroya Lei S, Chatterjee K, Henzinger TA. Hardware-optimal quantum algorithms.
    <i>Proceedings of the National Academy of Sciences</i>. 2025;122(12). doi:<a href="https://doi.org/10.1073/pnas.2419273122">10.1073/pnas.2419273122</a>
  apa: Muroya Lei, S., Chatterjee, K., &#38; Henzinger, T. A. (2025). Hardware-optimal
    quantum algorithms. <i>Proceedings of the National Academy of Sciences</i>. National
    Academy of Sciences. <a href="https://doi.org/10.1073/pnas.2419273122">https://doi.org/10.1073/pnas.2419273122</a>
  chicago: Muroya Lei, Stefanie, Krishnendu Chatterjee, and Thomas A Henzinger. “Hardware-Optimal
    Quantum Algorithms.” <i>Proceedings of the National Academy of Sciences</i>. National
    Academy of Sciences, 2025. <a href="https://doi.org/10.1073/pnas.2419273122">https://doi.org/10.1073/pnas.2419273122</a>.
  ieee: S. Muroya Lei, K. Chatterjee, and T. A. Henzinger, “Hardware-optimal quantum
    algorithms,” <i>Proceedings of the National Academy of Sciences</i>, vol. 122,
    no. 12. National Academy of Sciences, 2025.
  ista: Muroya Lei S, Chatterjee K, Henzinger TA. 2025. Hardware-optimal quantum algorithms.
    Proceedings of the National Academy of Sciences. 122(12), e2419273122.
  mla: Muroya Lei, Stefanie, et al. “Hardware-Optimal Quantum Algorithms.” <i>Proceedings
    of the National Academy of Sciences</i>, vol. 122, no. 12, e2419273122, National
    Academy of Sciences, 2025, doi:<a href="https://doi.org/10.1073/pnas.2419273122">10.1073/pnas.2419273122</a>.
  short: S. Muroya Lei, K. Chatterjee, T.A. Henzinger, Proceedings of the National
    Academy of Sciences 122 (2025).
corr_author: '1'
date_created: 2025-04-06T22:01:32Z
date_published: 2025-03-25T00:00:00Z
date_updated: 2026-04-28T13:41:14Z
day: '25'
ddc:
- '000'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1073/pnas.2419273122
ec_funded: 1
external_id:
  isi:
  - '001459435600001'
  pmid:
  - '40106357'
file:
- access_level: open_access
  checksum: 83501b8a65ee5fdd3f5604fc28eddc22
  content_type: application/pdf
  creator: dernst
  date_created: 2025-04-07T11:42:22Z
  date_updated: 2025-04-07T11:42:22Z
  file_id: '19524'
  file_name: 2025_PNAS_Muroya.pdf
  file_size: 6805668
  relation: main_file
  success: 1
file_date_updated: 2025-04-07T11:42:22Z
fulldoi: https://doi.org/10.1073/pnas.2419273122
has_accepted_license: '1'
intvolume: '       122'
isi: 1
issue: '12'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc-nd/4.0/
month: '03'
oa: 1
oa_version: Published Version
pmid: 1
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Proceedings of the National Academy of Sciences
publication_identifier:
  eissn:
  - 1091-6490
  issn:
  - 0027-8424
publication_status: published
publisher: National Academy of Sciences
quality_controlled: '1'
related_material:
  link:
  - relation: software
    url: https://github.com/smml1996/algorithm_synthesis
  - description: News on ISTA website
    relation: press_release
    url: https://ista.ac.at/en/news/hardware-optimal-quantum-algorithms/
scopus_import: '1'
status: public
title: Hardware-optimal quantum algorithms
tmp:
  image: /images/cc_by_nc_nd.png
  legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
  name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
    (CC BY-NC-ND 4.0)
  short: CC BY-NC-ND (4.0)
type: journal_article
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 122
year: '2025'
...