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

[Gus Gutoski]

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/20140116/40d12d3c/attachment.html>