- NSF project: CCF 0622201
- PI: Andreas Klappenecker

A quantum computer initializes, stores, and manipulates information using the states of quantum mechanical systems. This has the tremendous benefit that some computational problems can be solved much more efficiently on a quantum computer than on any classical computer. However, engineering a quantum computer is a highly nontrivial task. One of the main conceptual problems of quantum computing is that information stored in the state of a quantum system can get altered over time due to unavaidable interactions with surrounding quantum systems, an effect that is called decoherence. A remedy to this fundamental problem is to protect the quantum information with the help of quantum error-correcting codes. There is an additional complication, though, as active quantum error correction cannot be entirely error free, and might introduce new errors when trying to correct existing ones.

In this project, we developed families of so-called impure quantum codes that have the feature that no error correction is required for some error that are likely to occur, and therefore fewer active error correction steps will be needed. We further developed the theory of subsystem codes that allow one to balance active and passive error correction. We introduced the new theory of subsystem codes for quantum systems of various different levels that is beneficial for fault-tolerant quantum computation. We developed encoding algorithms for subsystem codes. Furthermore, we found decoding algorithms for a class of subsystem codes that are faster than the decoding of stabilizer codes. These decoding algorithms have the benefit that they can take advantage of any improvement of decoding algorithms for the underlying classical codes. We developed the theory of stabilizer codes over the integers modulo m; these are codes that use a simpler arithmetic that the arithmetic of finite fields that is commonly used to contruct quantum error-correcting codes. We also found estimates for the cod- ing capacity of classical network codes and proved that quantum entanglement is beneficial for evaluation of functions in a distributed setting.

The project supported (partially or fully) five graduate students, including two female students. The project contributed to class materials for a course on quantum algorithms and for a course on randomized algorithms. A inter- departmental and interdisciplinary quantum computing seminar was organized that was attended by faculty and students of the departments of Computer Sci- ence and Engineering, Electrical and Computer Engineering, Mathematics, and Physics, as well as member of the local industry.

We are grateful to NSF for supporting this research through award NSF CCF 0622201.

The following publications resulted from this project:

- A. Klappenecker
**On a Generalization of Clifford Codes**

10th Asian Conference on Quantum Information Science, AQIS'10, 2010 - A. Klappenecker
**Clifford Subsystem Codes**

IEEE International Symposium on Information Theory, ISIT 2010, pages 2667-2671, 2010 - A. Klappenecker, H. Lee, and J.L. Welch
**Scheduling Sensors by Tiling Lattices**

Parallel Processing Letters, 20(1), pages 3-13, 2010 - P.K. Sarvepalli and A. Klappenecker
**Degenerate quantum codes and the quantum Hamming bound**

Physical Review A, 81:032318, 2010 - P.K. Sarvepalli and A. Klappenecker.
**Encoding Subsystem Codes**

Intl. J. on Advances in Security, 2(3):142-155, 2009.

[All Formats] - P.K. Sarvepalli, A. Klappenecker, and M. Röttler.
**Asymmetric Quantum Codes: Constructions, Bounds, and Performance.**

Proc. Royal Society A, 465:1645-1672, 2009. - S.A. Aly and A. Klappenecker.
**Constructions of Subsystem Codes over Finite Fields.**

Intl. J. of Quantum Information, 7(5):891-912, 2009.

[All Formats] -
P.K. Sarvepalli, M. Röttler, and A. Klappenecker.
**New Decoding Algorithms for Generalized Shor Codes and a Class of Subsystem Codes.**

In Intl. Symp. Inform. Theory, Seoul, Korea, 2009, IEEE Press, 2009. - P.K. Sarvepalli and A. Klappenecker.
**Encoding subsystem codes with and without noisy gauge qubits.**

In The Third International Conference on Quantum, Nano and Micro Technologies, 2009. (Best Paper Award). - A. Klappenecker, A., H. Lee, and J.L. Welch, J.L.
**Scheduling Sensors by Tiling Lattices**

Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, PODC 2008, Toronto, Canada, August 18-21, 2008, page 437, 2008.

[extended version] - A. Klappenecker and P.K. Sarvepalli
**Clifford Code Constructions of Operator Quantum Error-Correcting Codes**

IEEE Transactions on Information Theory, 54(12), pages 5760-5765, 2008

[all formats] - S.A. Aly and A. Klappenecker
**Subsystem code constructions**

IEEE International Symposium on Information Theory, 2008. ISIT 2008, pages 369-373, 2008

[all formats] - Z. Kong, S.A. Aly, E. Soljanin, E. Yan, and A. Klappenecker
**Network Coding Capacity of Random Wireless Networks under a Signal-to-Interference-and-Noise Model**

In: Proc. of the 45th Annual Allerton Conference on Communication, Control, and Computing, 2007

[all formats] - S.A. Aly, M. Grassl, A. Klappenecker, M. Rötteler, and P.K. Sarvepalli
**Quantum Convolutional BCH Codes**

In: 10th Canadian Workshop on Information Theory, June 6-8th, Edmonton, Canada, 2007

[all formats] - A. Klappenecker and P.K. Sarvepalli
**On Subsystem Codes beating the quantum Hamming or Singleton Bound**

Proc. Roy. Soc. A. 463, pages 2887-2905, 2007

[all formats] - S.A. Aly, A. Klappenecker, and P.K. Sarvepalli
**Quantum Convolutional Codes derived from Generalized Reed-Solomon codes**

In: Proc. 2007 IEEE Intl. Symposium on Information Theory, 24-29th June, Nice, France, 2007 - S.A. Aly, A. Klappenecker, and P.K. Sarvepalli
**Duadic group algebra codes**

In: Proc. 2007 IEEE Intl. Symposium on Information Theory, 24-29th June, Nice, France, 2007

[all formats] - P.K. Sarvepalli, S.A. Aly, and A. Klappenecker
**Nonbinary Stabilizer Codes**

In: "The Mathematics of Quantum Computation and Quantum Technology", G. Chen, L. Kauffman, and S. Lomonaco (eds.), 2007

[pdf] - S.A. Aly, A. Klappenecker, P.K. Sarvepalli
**On Quantum and Classical BCH Codes**

IEEE Trans. Inform. Theory, March 2007

[all formats] - S.A. Aly, V. Kapoor, J. Meng, and A. Klappenecker
**Bounds on the network coding capacity for wireless random networks**

NetCod'07, 2007

[all formats] - S.A. Aly, A. Klappenecker, and P.K. Sarvepalli
**Subsystem codes**

44th Annual Allerton Conference on Communication, Control, and Computing, Monticello, Illinois, 2006

[all formats]