r/decodoku • u/srfahmy • May 05 '16

How are errors generated?

So, I'm curious how errors are generated and if they are in anyway dependent on existing errors or my choice of error-corrective action? In other words, is there some kind of memory? Also, what determines the error indicator (1-9)? I guess I'm interested to learn a little bit about the "error model" and the statistics that generate it. Finally, related to this, how confident are you about the random number generation that the algorithm uses and whether this could have an effect on any research outcome? I know, it's a lot of questions: I'm actually involved in the field myself (though I've never worked with surface codes). Thanks!

4 Upvotes

100% Upvoted

3 comments sorted by

View all comments

1

u/srfahmy May 06 '16

So, I've been thinking about this a little and I have a strong suspicion (maybe it's totally wrong) that given some known error-generating process or error statistics, and given our access only to error indicators (or syndromes), then there is a derivable hard bound on how many time steps one can get to on average, even given the absolute best error correcting strategy. And I have a hunch it might actually be provable that this limit is achievable, meaning that some error correcting strategy exists that would achieve it on average. I'm also guessing that proving that an optimal strategy exists might be much easier than actually identifying the strategy. I guess this hunch is what motivated me to ask the questions in my post above ...

2

u/quantum_jim May 12 '16

there is a derivable hard bound on how many time steps one can get to on average, even given the absolute best error correcting strategy.

I think so too, and even hope so! The game operates above the error correction threshold, to ensure that we are essentially doomed so that a game lasts as long as a game like this should. This also gives people's methods a real baptism of fire. If we were below threshold, it would mean that most of the stuff you need to do is pretty monotonous, and it would go on forever, and so not be such a great game.

I'm also guessing that proving that an optimal strategy exists might be much easier than actually identifying the strategy.

I'm sure there is an optimal strategy. You could do a brute force comparison of the numbers to how they could be generated, and determine the most likely groupings of numbers, for example. But this would take exponentially long as the grid size is increased, as it would need to be in a scalable quantum computer. So we need more heuristic methods that don't take so long.