Papers Available Electronically

Right now, not all the papers listed below are linkable, since I forgot to move the appropriate page which I came here from AT&T. I am slowly getting them up, and updating this page. Many apologies for the delay. I have papers in the subjects of quantum computing and geometry and combinatorics available electronically as PostScript files or pdf files. Apologies for those pdf files where the pages appear in the wrong order. That's the way the converter produced them, and although I eventually may fix them, it will probably be a while. Some of these papers are earlier versions than the ones that appear in journals, and the journal versions may be slightly improved.

Many of my quantum computing papers have appeared on the Los Alamos preprint server and not have been put here yet, since I don't update this page often enough, or completely---if a paper is available on the preprint server, I don't take the trouble to put it here. So if you're looking for my latest papers, you should check there as well.
A quite out-of-date publications list (including papers not available electronically) is also on the web.

Quantum Computing

The following paper is the one on this page that's downloaded the most, so I'm putting it first. The others are roughly in inverse chronological order.

Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer (28 pages)

This paper shows that efficient algorithms for prime factorization and discrete logarithms exist on a quantum computer. It is a substantally expanded and revised version of my paper in the 1994 Symposium of Foundations on Computer Science (see below), and appears in the SIAM Journal of Computing 26, pp. 1484-1509 (1997).

This paper discusses recent progress (or lack of it) in quantum algorithms. It appeared in Quantum Information Processing in 2004, Vol. 3.

This paper is essentially the survey talk that I gave at the Visions in Mathematics - Towards 2000 conference in Tel Aviv, September 1999. It appears in Vol. 2 of the special issue of GAFA (Geometric and Functional Analysis) devoted to this conference.

This is a paper showing that there is an additional classical capacity of a quantum channel between the C₁ capacity, which is the capacity achievable by tensor product inputs and separate measurements on each channel use, and the Holevo capacity, which is achievable by tensor product inputs and joint measurements. This adaptive capacity uses tensor product inputs, and adaptive separate measurements, so the protocol for decoding the message uses local quantum operations on each channel output, but may use a classical computer with access to the outcomes all the measurements performed so far to decide which measurement or partial measurement to perform next. It also contains the results of the following paper, as it uses the same methods and the same counterexample channels. It appears in the special issue of the IBM Journal of Research and Development celebrating Charlie Bennett's 60th birthday: Vol. 64, pp. 115-138. For the arXiv, I compressed some of the figures to make the file sizes smaller, so if you want sharper figures, you can either go to the journal version (which did a wonderful job of typesetting the figures) or download the version here (PDF). (Warning: LARGE files; use the arXiv version above if you have a slow connection.)

This is a paper on the first part of a talk I presented at the 2000 Quantum Communication, Measurement and Computing conference. This paper shows that if you want to extract the most Shannon information from an ensemble of quantum states, and there are three states and three real dimensions, you may need a positive operator valued measurement with six elements, which is the upper bound given by Davies' theorem. This gives a counterexample to a conjecture that you could get by with d elements if you had an ensemble of d quantum states in d dimensions. If you have an ensemble of two quantum states, it is still unknown whether you need more than d elements (i.e., a more general measurement than a von Neumann measurement). Largely superceded by "The Adaptive Classical Capacity ..." paper above.

I presented a plenary talk on Quantum computing at the 1998 International Congress of Mathematicians. This is the associated paper that will appear in the Proceedings. It describes the quantum factoring algorithm and briefly sketches the basics of quantum error correction and quantum fault tolerant computation.

This is a survey on quantum information theory which will appear in the IEEE Transactions on Information Theory (October, 1998).

This shows how to construct states with bound (non-distillable) entanglement in a simpler manner than Horodecki's original construction of them, by relating them to unextendible product bases.

This paper constructs product bases in the joint state space of two quantum spaces, owned by A and B, which cannot be measured if A and B are constrained to communicate only classically, but can be measured if A and B can exchange quantum states.

This paper presents a family of quantum error-correcting codes whose capacity (slightly) exceeds that of random coding for very noisy channels; random codes had previously been conjectured to be optimal. To appear in Phys. Rev. A.

This paper derives a relationship between two different notions of fidelity (entanglement fidelity and ensemble fidelity) for a completely depolarizing quantum channel, which gives rise to a quantum analog of the MacWilliams identities from classical coding theory. Classically, these identities provided a powerful tool for investigating the possible existence of codes. The same techniques can be applied to the quantum case. Appeared in Phys. Rev. Lett. 78, pp. 1600-1603 (1997).

This paper follows up on the paper "Quantum error correction and orthogonal geometry" (below) by showing how to obtain quantum error-correcting codes from certain classical error-correcting codes over the field GF(4). We find many new quantum error-correcting codes and obtain upper and lower bounds for this type of quantum error-correcting code. Revised August, 1997. To appear in IEEE Transactions on Information Theory.

This paper shows how to detect and correct errors in codes obtained through orthogonal geometry. The procedure is relatively simple and can be made resistant to errors in the correcting process. It appeared in Phys. Rev. Lett. 77, pp. 3260-3263 (1996).

This paper shows how to obtain fault-tolerant quantum computation using quantum error-correcting codes. It appeared in the Proceedings of the 1996 Symposium on Foundations of Computer Science, held in Burlington, Vermont.

This paper gives a combinatorial method of constructing quantum error-correcting codes that are somewhat analogous to linear codes in classical coding theory. Most known quantum codes fall into this class. Appeared in Phys. Rev. Lett. 78, pp. 405-408 (1997).

This paper shows that quantum error-correcting codes that do not completely reveal the error syndrome can transmit quantum information through channels too noisy for any code that does completely reveal the syndrome, thereby showing that codes exist that can do better than the quantum analog of the Shannon bound for the capacity of a noisy channel. It is the original version of the paper "Quantum channel capacity of very noisy channels" (see above).

This paper shows how to construct quantum error-correcting codes that can correct more than one error, and which asymptotically increase the amount of storage required for quantum data only by a 1+o(1) factor as the block length goes to infinity. This paper appeared in Phys. Rev. A 54, pp. 1098-1106 (1996).

This paper appeared in Phys. Rev. A 52, pp. R2493-2496 (1995). It shows that error-correcting codes can be devised for encoding quantum information.

This paper appeared in Phys. Rev. A 52, pp. 3457-3467 (1995). It studies which sets of quantum gates are sufficient for universal quantum computation.

This paper is the original paper showing that factoring and discrete logarithms can be done quickly on a quantum computer. It appeared in the 1994 Symposium on Foundations of Computer Science, held in Santa Fe, New Mexico. Minor changes have been made in this version to correct a few errors and to add a figure.

Geometry

In chronological order: Random Planar Matching and Bin packing, by Peter W. Shor

My thesis. This should fall under the heading of computer science, geometry, combinatorics, and probability, but I'm arbitrarily just putting it under geometry.

This paper contains two results: my proof that stretchability of pseudoline arrangements is NP-hard, and a stronger result of Mnev (for which I provided a somewhat simplified proof), which shows that the realization space of line arrangements (i.e., oriented matroids) can realize the realization space of any semiaglebraic set. It appeared in Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift (P. Gritzman & B. Sturmfels, eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science Vol. 4, American Math. Soc., Providence, RI, pp. 531-554 (1991).

This paper gives a counterexample to a 1930 conjecture of O. H. Keller. The conjecture was that any tiling of Euclidean n-space by unit cubes contains two cubes meeting in a full (n-1)-dimensional face. This appeared in Bull. Amer. Math. Soc. 27, pp. 279-283 (1992). The next paper builds on these results.

This paper is a followup to the previous paper, "Keller's cube-tiling conjecture is false in high dimensions," and shows that there are cube tilings in n dimensions such that no cubes have a common face of dimension n - c root(n), for some constant c. It also gives a 10-dimensional tiling where no two cubes share a complete 8-dimensional face. It appeared in Discrete and Computational Geometry 11, pp. 359-391 (1994).

This paper gives a family of optimal packings in Grassmannian manifolds related to a group which also appears in quantum error-correcting codes. It was published in J. of Algebraic Combinatorics 7, pp. 157-163 (1998). This is a follow-up to the paper Packing Lines, Planes, etc.: Packings in Grassmannian Space, J. H. Conway, R. H. Hardin and N. J. A. Sloane, Experimental Math. 5, pp. 139-159 (1996).

This paper builds on the previous paper to give more good packings of 2^k dimensional subspaces in 2ⁱ dimensional Euclidean space.

Combinatorics

After 25 years, Pooya Hatami found a bug in the first paper I wrote. The fact that it took so long shows just how incomprehensible this paper was. We have vastly improved the writing, so that now it is much more comprehensible, and corrected the bug. The JCT A version has some minor typos corrected, so you might want to use that if you can access it.

Up to my homepage.