Questions tagged [fault-tolerance]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
8 votes
1 answer
164 views

What are the general direction and target question in the field of quantum error correction?

After quantum error correction was introduced in mid '90s, in subsequent years many of the classical analogues regarding the structure of code (such as singleton bound, GV bound etc) were obtained in ...
Root's user avatar
  • 387
2 votes
0 answers
69 views

What is the error bound in the classical error threshold theorem?

For unreliable classical computation there is an error threshold theorem due to von Neumann analogous to the quantum error threshold theorem that shows that even if gates produce the wrong result at ...
Anders Sandberg's user avatar
1 vote
0 answers
119 views

Non-Transversal Fault Tolerant Gate

I have always heard that transversality is a sufficient, not a necessary condition for fault-tolerance in quantum computation. However, I have never seen any examples of non-transversal fault tolerant ...
ruadath's user avatar
  • 441
10 votes
1 answer
573 views

What is the advantage of designing deterministic distributed algorithms?

Distributed algorithms that are resilient to failures can either be deterministic or probabilistic. Take for example the consensus problem. Paxos is deterministic in the sense that given the ...
danyhow's user avatar
  • 201
33 votes
4 answers
4k views

Does a noisy version of Conway's game of life support universal computation?

Quoting Wikipedia, "[Conway's Game of Life] has the power of a universal Turing machine: that is, anything that can be computed algorithmically can be computed within Conway's Game of Life." Do such ...
Gil Kalai's user avatar
  • 6,013
5 votes
1 answer
125 views

Honest Majority unconditional coinflipping without private channels

All communication is assumed to be by the parties taking turns making authenticated broadcasts. Is there a way for $n$ parties, each with access to ideal local randomness, to jointly choose a ...
user avatar
8 votes
1 answer
2k views

Fault-tolerant programming languages / paradigms?

I've been passively thinking for a long time, what could be the foundation for programming systems that can tolerate their own and other systems' bugs (not even speaking of environmental conditions ...
jkff's user avatar
  • 8,941
24 votes
2 answers
161 views

What is the best lower bound for the fault-tolerance threshold in quantum computing?

It is well established that there exists a noise threshold for quantum computation, such that below this threshold, the computation can be encoded in such a way that it yields the correct result with ...
Joe Fitzsimons's user avatar