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.

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 1994Progress in Quntum Algorithms by Peter Shor (7 pages)Symposium of Foundations on Computer Science(see below), and appears in theSIAM Journal of Computing26,pp. 1484-1509 (1997).

This paper discusses recent progress (or lack of it) in quantum algorithms. It appeared inQuantum information theory: Results and open problems (PDF) by Peter Shor (19 pages)Quantum Information Processingin 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.The adaptive classical capacity of a quantum channel, or information capacities of three symmetric pure states in three dimensions. by Peter Shor (44 pages)

This is a paper showing that there is an additional classical capacity of a quantum channel between the COn the Number of Elements Needed in a POVM Attaining the Accessible Information (QCM&C Proceedings Paper) by Peter Shor (8 pages)_{1}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 withQuantum Computing (ICM Proceedings Paper) (PDF) by Peter Shor (20 pages)delements if you had an ensemble ofdquantum states inddimensions. If you have an ensemble of two quantum states, it is still unknown whether you need more thandelements (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.Quantum Information Theory (Postscript) (Postscript) or (PDF), by Charles H. Bennett and Peter Shor (52 pages)

This is a survey on quantum information theory which will appear in theUnextendible Product Bases and Bound Entanglement (Postscript) by David P. Divincenzo, Tal Mor, Peter Shor, John A. Smolin and Barbara M. Terhal (4 pages)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.Quantum Nonlocality without Entanglement (Postscript) by Charles H. Bennett, D P. DiVincenzo, Christopher A. Fuchs, Tal Mor, Eric Rains, Peter W. Shor, John A. Smolin and William K. Wootters (30 pages)

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.Quantum channel capacity of very noisy channels by D. P. DiVincenzo, P. W. Shor and J. A. Smolin (31 pages)

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 inQuantum analog of the MacWilliams identities in classical coding theory (Postscript) or (PDF), by P. Shor and R. Laflamme (9 pages)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 inQuantum error correction via codes over GF(4) or (PDF), by A. R. Calderbank, E. Rains, P. W. Shor, and N. J. A. Sloane (34 pages)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 inFault-tolerant error correction with efficient quantum codes (Postscript) or (PDF), by D. P. DiVincenzo and P. W. Shor (12 pages)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 inFault-tolerant quantum computation (Postscript) or (PDF), (10 pages)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 1996Quantum error correction and orthogonal geometry by A. R. Calderbank, E. Rains, P. W. Shor, and N. J. A. Sloane (13 pages)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 inQuantum error-correcting codes need not completely reveal the error syndrome (Postscript) or (PDF), by P. W. Shor and J. A. Smolin (13 pages)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).Good quantum error-correcting codes exist by A. R. Calderbank and P. W. Shor (22 pages)

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 inScheme for reducing decoherence in quantum memory (Postscript) or (PDF), (4 pages)Phys. Rev. A54,pp. 1098-1106 (1996).

This paper appeared inElementary gates for quantum computationPhys. Rev. A52,pp. R2493-2496 (1995). It shows that error-correcting codes can be devised for encoding quantum information.

by A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. W. Shor, T. Sleator, J. Smolin, and H. Weinfurter (24 pages)

This paper appeared inAlgorithms for quantum computation: Discrete logarithms and factoring (Postscript) or (PDF), (11 pages)Phys. Rev. A52,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 1994Symposium 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.

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.Stretchability of pseudoline arrangements is NP-hard, by Peter W. Shor

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 inKeller's cube-tiling conjecture is false in high dimensions (PDF) by J. C. Lagarias and P. W. Shor (6 pages)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 inCube tilings ofBull. 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 inA family of optimal packings in Grassmannian manifolds (PDF) by Peter W. Shor and Neil J. A. Sloane (8 pages)Discrete and Computational Geometry11,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 inA group-theoretic framework for the construction of packings in Grassmannian spaces (Postscript) or (PDF), by A. R. Calderbank, R. H. Hardin, E. M. Rains, P. W. Shor and N. J. A. Sloane (14 pages)J. of Algebraic Combinatorics7,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^{i}dimensional Euclidean space.

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.