Feynman Meets Turing: The Infeasibility of Digital Compilers for Gate-Based Quantum Computing

Yannik N. Bock, Holger Boche, Zoe Garcia Del Toro, Frank H.P. Fitzek

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Scopus citations

Abstract

We consider the problem of computing gate-circuit approximations of quantum algorithms, i.e., unitary operators, from the perspective of computable (effective) analysis. The scientific community thinks the Solovay-Kitaev theorem a mile-stone in quantum compiling - the task of computing gate-circuit approximations - because it proves the existence of efficient quantum compilers in an analytic sense. However, since we cannot represent unitary operators in a mere analytical way on digital computers, contemporary digital implementations of quantum compiling resort to heuristic numerics and remain below the computational performance engineers hope to realize using the result of Solovay and Kitaev. This paper discusses quantum compiling within a framework of computable analysis, establishing a concept of computable unitary operators for digital computing based on the theory of Turing machines. Particularly, we prove that digital quantum compiling is uncomputable due to the underlying algebraic structure. Finally, we discuss several implications of our findings for heuristic digital implementations of quantum compiling, hinting toward possible research directions to thoroughly understand the relevant bottlenecks.

Original languageEnglish
Title of host publicationICC 2024 - IEEE International Conference on Communications
EditorsMatthew Valenti, David Reed, Melissa Torres
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2440-2445
Number of pages6
ISBN (Electronic)9781728190549
DOIs
StatePublished - 2024
Event59th Annual IEEE International Conference on Communications, ICC 2024 - Denver, United States
Duration: 9 Jun 202413 Jun 2024

Publication series

NameIEEE International Conference on Communications
ISSN (Print)1550-3607

Conference

Conference59th Annual IEEE International Conference on Communications, ICC 2024
Country/TerritoryUnited States
CityDenver
Period9/06/2413/06/24

Keywords

  • quantum algorithm
  • quantum compiler
  • quantum computing
  • Solovay-Kitaev theorem
  • Turing machine

Fingerprint

Dive into the research topics of 'Feynman Meets Turing: The Infeasibility of Digital Compilers for Gate-Based Quantum Computing'. Together they form a unique fingerprint.

Cite this