Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1106.0485

How Quantum Computers Fail: Quantum Codes, Correlations in Physical Systems, and Noise Accumulation

Gil Kalai

Published Jun 2, 2011• 53 citations
arXivHTMLPDF

Abstract

The feasibility of computationally superior quantum computers is one of the most exciting and clear-cut scientific questions of our time. The question touches on fundamental issues regarding probability, physics, and computability, as well as on exciting problems in experimental physics, engineering, computer science, and mathematics. We propose three related directions towards a negative answer. The first is a conjecture about physical realizations of quantum codes, the second has to do with correlations in stochastic physical systems, and the third proposes a model for quantum evolutions when noise accumulates. The paper is dedicated to the memory of Itamar Pitowsky.

DOI
10.48550/arxiv.1106.0485

Related papers

QUANTUM COMPUTATION

Dorit Aharonov

In the last few years, theoretical study of quantum systems serving as computational devices has achieved tremendous progress. We now have strong theoretical evidence that quantum computers, if built, might be used as a dramatically powerful computational tool. This review is about to tell the story of theoretical quantum computation. I left out the developing topic of experimental realizations of the model, and neglected other closely related topics which are quantum information and quantum communication. As a result of narrowing the scope of this paper, I hope it has gained the benefit of being an almost self contained introduction to the exciting field of quantum computation. The review begins with background on theoretical computer science, Turing machines and Boolean circuits. In light of these models, I define quantum computers, and discuss the issue of universal quantum gates. Quantum algorithms, including Shor's factorization algorithm and Grover's algorithm for searching databases, are explained. I will devote much attention to understanding what the origins of the quantum computational power are, and what the limits of this power are. Finally, I describe the recent theoretical results which show that quantum computers maintain their complexity power even in the presence of noise, inaccuracies and finite precision. I tried to put all results in their context, asking what the implications to other issues in computer science and physics are. In the end of this review I make these connections explicit, discussing the possible implications of quantum computation on fundamental physical questions, such as the transition from quantum to classical physics.

arXiv:quant-ph/9812037•WORLD SCIENTIFIC eBooks•Mar 1, 1999•139 citations

Practical Advances in Quantum Error Correction & Communication

Daniel Benjamin Criger

Quantum computing exists at the intersection of mathematics, physics, chemistry, and engineering; the main goal of quantum computing is the creation of devices and algorithms which use the properties of quantum mechanics to store, manipulate and measure information. There exist many families of algorithms, which, using non-classical logical operations, can outperform traditional, classical algorithms in terms of memory and processing requirements. In addition, quantum computing devices are fundamentally smaller than classical processors and memory elements; since the physical models governing their performance are applicable on all scales, as opposed to classical logic elements, whose underlying principles rely on the macroscopic nature of the device in question. \n \nQuantum algorithms, for the most part, are predicated on a theory of resources. It is often assumed that quantum computers can be placed in a precise fiducial state prior to computation, and that logical operations are perfect, inducing no error on the system which they affect. These assumptions greatly simplify algorithmic design, but are fundamentally unrealistic. In order to justify their use, it is necessary to develop a framework for using a large number of imperfect devices to simulate the action of a perfect device, with some acceptable probability of failure. This is the study of fault-tolerant quantum computing. In order to pursue this study effectively, it is necessary to understand the fundamental nature of generic quantum states and operations, as well as the means by which one can correct quantum errors. Additionally, it is important to attempt to minimize the use of computational resources in achieving error reduction and fault-tolerant computing. \n \nThis thesis is concerned with three projects related to the use of error-prone quantum systems to transmit and manipulate information. The first of these is concerned with the use of imperfectly-prepared states in error-correction routines. Using optimal quantum error correction, we are able to deduce a method of partially protecting encoded quantum information against preparation errors prior to encoding, using no additional qubits. The second of these projects details the search for entangled states which can be used to transmit classical information over quantum channels at a rate superior to classical states. The third of these projects concerns the transcoding of data from one quantum code into another using few ancillary resources. The descriptions of these projects are preceded by a brief introduction to representations of quantum states and channels, for completeness. \n \nThree techniques of general interest are presented in appendices. The first is an introduction to, and a minor advance in the development of optimal error correction codes. The second is a more efficient means of calculating the action of a quantum channel on a given state, given that the channel acts non-trivially only on a subsystem, rather than the entire system. Finally, we include documentation on a software package developed to aid the search for quantum transcoding operations.

•Oct 25, 2013•1 citation

Quantum Stochastic Processes and Quantum Many-Body Physics

Johannes Bausch

This dissertation investigates the theory of quantum stochastic processes and its applications in quantum many-body physics. The main goal is to analyse complexity-theoretic aspects of both static and dynamic properties of physical systems modelled by quantum stochastic processes. The thesis consists of two parts: the first one addresses the computational complexity of certain quantum and classical divisibility questions, whereas the second one addresses the topic of Hamiltonian complexity theory. In the divisibility part, we discuss the question whether one can efficiently sub-divide a map describing the evolution of a system in a noisy environment, i.e. a CPTP- or stochastic map for quantum and classical processes, respectively, and we prove that taking the nth root of a CPTP or stochastic map is an NP-complete problem. Furthermore, we show that answering the question whether one can divide up a random variable $X$ into a sum of $n$ iid random variables $Y_i$, i.e. $X=\sum_{i=1}^n Y_i$, is poly-time computable; relaxing the iid condition renders the problem NP-hard. In the local Hamiltonian part, we study computation embedded into the ground state of a many-body quantum system, going beyond "history state" constructions with a linear clock. We first develop a series of mathematical techniques which allow us to study the energy spectrum of the resulting Hamiltonian, and extend classical string rewriting to the quantum setting. This allows us to construct the most physically-realistic QMAEXP-complete instances for the LOCAL HAMILTONIAN problem (i.e. the question of estimating the ground state energy of a quantum many-body system) known to date, both in one- and three dimensions. Furthermore, we study weighted versions of linear history state constructions, allowing us to obtain tight lower and upper bounds on the promise gap of the LOCAL HAMILTONIAN problem in various cases. We finally study a classical embedding of a Busy Beaver Turing Machine into a low-dimensional lattice spin model, which allows us to dictate a transition from a purely classical phase to a Toric Code phase at arbitrarily large and potentially even uncomputable system sizes.

•Oct 4, 2017•1 citation

How Quantum Computers Can Fail

Gil Kalai

We propose and discuss two postulates on the nature of errors in highly correlated noisy physical stochastic systems. The first postulate asserts that errors for a pair of substantially correlated elements are themselves substantially correlated. The second postulate asserts that in a noisy system with many highly correlated elements there will be a strong effect of error synchronization. These postulates appear to be damaging for quantum computers.

arXiv:quant-ph/0607021•Jul 4, 2006•11 citations

Useful Mathematical Relations

Anthony F. J. Levi

Featuring new coverage of quantum engineering and quantum information processing, the third edition of this bestselling textbook continues to provide a uniquely practical introduction to the fundamentals of quantum mechanics. It features straightforward explanations of quantum effects, suitable for readers from all backgrounds; real-world engineering problems showcasing the practical application of theory to practice, providing a relevant and accessible introduction to cutting-edge quantum applications; over 60 accessible worked examples using MATLAB (as well as open-source Python), allowing deepened understanding through computational exploration and visualization; and a new chapter on quantum engineering, introducing state-of-the-art concepts in quantum information processing and quantum device design. Updated throughout and supported online by downloadable MATLAB code, exam questions, and solutions to over 150 homework problems for instructors, this is the ideal textbook for senior undergraduate and graduate students in applied science, applied physics, engineering, and materials science studying a first course in quantum mechanics.

Cambridge University Press eBooks•Aug 31, 2023•0 citations

Quantum Computers - How Can They Fail?

Gil Kalai

We propose and discuss two postulates on the nature of errors in highly correlated noisy physical stochastic systems. The first postulate asserts that errors for a pair of substantially correlated elements are themselves substantially correlated. The second postulate asserts that in a noisy system with many highly correlated elements there will be a strong effect of error synchronization. These postulates appear to be damaging for quantum computers.

•Jan 1, 2006•0 citations
The feasibility of computationally superior quantum computers is one of the most exciting and clear-cut scientific questions of our time. The question touches on fundamental issues regarding probability, physics, and computability, as well as on exciting problems in experimental physics, engineering, computer science, and mathematics. We propose three related directions towards a negative answer. The first is a conjecture about physical realizations of quantum codes, the second has to do with correlations in stochastic physical systems, and the third proposes a model for quantum evolutions when noise accumulates. The paper is dedicated to the memory of Itamar Pitowsky.
In the last few years, theoretical study of quantum systems serving as computational devices has achieved tremendous progress. We now have strong theoretical evidence that quantum computers, if built, might be used as a dramatically powerful computational tool. This review is about to tell the story of theoretical quantum computation. I left out the developing topic of experimental realizations of the model, and neglected other closely related topics which are quantum information and quantum communication. As a result of narrowing the scope of this paper, I hope it has gained the benefit of being an almost self contained introduction to the exciting field of quantum computation. The review begins with background on theoretical computer science, Turing machines and Boolean circuits. In light of these models, I define quantum computers, and discuss the issue of universal quantum gates. Quantum algorithms, including Shor's factorization algorithm and Grover's algorithm for searching databases, are explained. I will devote much attention to understanding what the origins of the quantum computational power are, and what the limits of this power are. Finally, I describe the recent theoretical results which show that quantum computers maintain their complexity power even in the presence of noise, inaccuracies and finite precision. I tried to put all results in their context, asking what the implications to other issues in computer science and physics are. In the end of this review I make these connections explicit, discussing the possible implications of quantum computation on fundamental physical questions, such as the transition from quantum to classical physics.
Quantum computing exists at the intersection of mathematics, physics, chemistry, and engineering; the main goal of quantum computing is the creation of devices and algorithms which use the properties of quantum mechanics to store, manipulate and measure information. There exist many families of algorithms, which, using non-classical logical operations, can outperform traditional, classical algorithms in terms of memory and processing requirements. In addition, quantum computing devices are fundamentally smaller than classical processors and memory elements; since the physical models governing their performance are applicable on all scales, as opposed to classical logic elements, whose underlying principles rely on the macroscopic nature of the device in question. \n \nQuantum algorithms, for the most part, are predicated on a theory of resources. It is often assumed that quantum computers can be placed in a precise fiducial state prior to computation, and that logical operations are perfect, inducing no error on the system which they affect. These assumptions greatly simplify algorithmic design, but are fundamentally unrealistic. In order to justify their use, it is necessary to develop a framework for using a large number of imperfect devices to simulate the action of a perfect device, with some acceptable probability of failure. This is the study of fault-tolerant quantum computing. In order to pursue this study effectively, it is necessary to understand the fundamental nature of generic quantum states and operations, as well as the means by which one can correct quantum errors. Additionally, it is important to attempt to minimize the use of computational resources in achieving error reduction and fault-tolerant computing. \n \nThis thesis is concerned with three projects related to the use of error-prone quantum systems to transmit and manipulate information. The first of these is concerned with the use of imperfectly-prepared states in error-correction routines. Using optimal quantum error correction, we are able to deduce a method of partially protecting encoded quantum information against preparation errors prior to encoding, using no additional qubits. The second of these projects details the search for entangled states which can be used to transmit classical information over quantum channels at a rate superior to classical states. The third of these projects concerns the transcoding of data from one quantum code into another using few ancillary resources. The descriptions of these projects are preceded by a brief introduction to representations of quantum states and channels, for completeness. \n \nThree techniques of general interest are presented in appendices. The first is an introduction to, and a minor advance in the development of optimal error correction codes. The second is a more efficient means of calculating the action of a quantum channel on a given state, given that the channel acts non-trivially only on a subsystem, rather than the entire system. Finally, we include documentation on a software package developed to aid the search for quantum transcoding operations.
This dissertation investigates the theory of quantum stochastic processes and its applications in quantum many-body physics. The main goal is to analyse complexity-theoretic aspects of both static and dynamic properties of physical systems modelled by quantum stochastic processes. The thesis consists of two parts: the first one addresses the computational complexity of certain quantum and classical divisibility questions, whereas the second one addresses the topic of Hamiltonian complexity theory. In the divisibility part, we discuss the question whether one can efficiently sub-divide a map describing the evolution of a system in a noisy environment, i.e. a CPTP- or stochastic map for quantum and classical processes, respectively, and we prove that taking the nth root of a CPTP or stochastic map is an NP-complete problem. Furthermore, we show that answering the question whether one can divide up a random variable XXX into a sum of nnn iid random variables YiY_iYi​, i.e. X=∑i=1nYiX=\sum_{i=1}^n Y_iX=∑i=1n​Yi​, is poly-time computable; relaxing the iid condition renders the problem NP-hard. In the local Hamiltonian part, we study computation embedded into the ground state of a many-body quantum system, going beyond "history state" constructions with a linear clock. We first develop a series of mathematical techniques which allow us to study the energy spectrum of the resulting Hamiltonian, and extend classical string rewriting to the quantum setting. This allows us to construct the most physically-realistic QMAEXP-complete instances for the LOCAL HAMILTONIAN problem (i.e. the question of estimating the ground state energy of a quantum many-body system) known to date, both in one- and three dimensions. Furthermore, we study weighted versions of linear history state constructions, allowing us to obtain tight lower and upper bounds on the promise gap of the LOCAL HAMILTONIAN problem in various cases. We finally study a classical embedding of a Busy Beaver Turing Machine into a low-dimensional lattice spin model, which allows us to dictate a transition from a purely classical phase to a Toric Code phase at arbitrarily large and potentially even uncomputable system sizes.
Featuring new coverage of quantum engineering and quantum information processing, the third edition of this bestselling textbook continues to provide a uniquely practical introduction to the fundamentals of quantum mechanics. It features straightforward explanations of quantum effects, suitable for readers from all backgrounds; real-world engineering problems showcasing the practical application of theory to practice, providing a relevant and accessible introduction to cutting-edge quantum applications; over 60 accessible worked examples using MATLAB (as well as open-source Python), allowing deepened understanding through computational exploration and visualization; and a new chapter on quantum engineering, introducing state-of-the-art concepts in quantum information processing and quantum device design. Updated throughout and supported online by downloadable MATLAB code, exam questions, and solutions to over 150 homework problems for instructors, this is the ideal textbook for senior undergraduate and graduate students in applied science, applied physics, engineering, and materials science studying a first course in quantum mechanics.