[quantum-info] PIQuDos seminar on Wed Jan 22: Pavithran Iyer

[Gus Gutoski]

Reminder: PIQuDos seminar by Pavithran Iyer tomorrow at 16:00 in the Time
room.  -Gus


On Thu, Jan 16, 2014 at 9:55 AM, Gus Gutoski <ggutoski at perimeterinstitute.ca
> wrote:

> Please join us on Wednesday, January 22 at 4pm in the Time room for a
> quantum information seminar by Pavithran Iyer.
>
> Title: *Hardness of correcting errors on a stabilizer code*
> Speaker: *Pavithran Iyer* (Université de Sherbrooke)
>
> Abstract: Problems in computer science are often classified based on the
> scaling of the runtimes for algorithms that can solve the problem. Easy
> problems are efficiently solvable but often in physics we encounter
> problems that take too long to be solved on a classical computer. Here we
> look at one such problem in the context of quantum error correction. We
> will further show that no efficient algorithm for this problem is likely to
> exist.
>
> We will address the computational hardness of a decoding problem,
> pertaining to quantum stabilizer codes considering independent X and Z
> errors on each qubit. Much like classical linear codes, errors are detected
> by measuring certain check operators which yield an error syndrome, and the
> decoding problem consists of determining the most likely recovery given the
> syndrome. The corresponding classical problem is known to be NP-Complete,
> and a similar decoding problem for quantum codes is known to be NP-Complete
> too. However, this decoding strategy is not optimal in the quantum setting
> as it does not take into account error degeneracy, which causes distinct
> errors to have the same effect on the code. Here, we show that optimal
> decoding of stabilizer codes is computationally much harder than optimal
> decoding of classical linear codes, it is #P-Complete.
>
> Date: Wednesday, January 22, 2014.
> Time: 16:00
> Location: Time Room (294)
>
> -Gus
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.uwaterloo.ca/pipermail/quantum-info/attachments/20140121/ef5cd64a/attachment.html>