Questions tagged [fault-tolerance]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
87 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 ...
10
votes
1answer
432 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 ...
30
votes
4answers
3k 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 ...
5
votes
1answer
120 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 ...
7
votes
1answer
1k 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 ...
24
votes
2answers
95 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 ...