Publications (27)
Quantum state restoration and single-copy tomography
Edward Farhi, David Gosset, Avinatan Hassidim +3
Given a single copy of an n qubit quantum state |psi>, the no-cloning theorem greatly limits the amount of information which can be extracted from it. Moreover, given only a proced…
Time Independent Universal Computing with Spin Chains: Quantum Plinko Machine
Kevin Thompson, Can Gokler, Seth Lloyd +1
We present a scheme for universal quantum computing using XY Heisenberg spin chains. Information is encoded into packets propagating down these chains, and they interact with each…
Quantum Adiabatic Algorithms, Small Gaps, and Different Paths
Edward Farhi, Jeffrey Goldstone, David Gosset +3
We construct a set of instances of 3SAT which are not solved efficiently using the simplest quantum adiabatic algorithm. These instances are obtained by picking random clauses all…
The Learning Stabilizers with Noise problem
Alexander Poremba, Yihui Quek, Peter Shor
Random classical codes have good error correcting properties, and yet they are notoriously hard to decode in practice. Despite many decades of extensive study, the fastest known al…
The Power of Unentanglement
Scott Aaronson, Salman Beigi, Andrew Drucker +2
The class QMA(k), introduced by Kobayashi et al., consists of all languages that can be verified using k unentangled quantum proofs. Many of the simplest questions about this class…
Topological quantum computation assisted by phase transitions
Yuanjie Ren, Peter Shor
In this paper, we explore topological quantum computation augmented by subphases and phase transitions. We commence by investigating the anyon tunneling map, denoted as , betwe…
On bit-commitment based quantum coin flipping
Ashwin Nayak, Peter Shor
In this paper, we focus on a special framework for quantum coin flipping protocols,_bit-commitment based protocols_, within which almost all known protocols fit. We show a lower bo…
polylog-LDPC Capacity Achieving Codes for the Noisy Quantum Erasure Channel
Seth Lloyd, Peter Shor, Kevin Thompson
We provide sparse quantum codes for correcting the erasure channel arbitrarily close to the capacity. Specifically, we provide quantum stabilizer codes tha…
On quantum capacity of erasure channel assisted by back classical communication
Debbie Leung, Joungkeun Lim, Peter Shor
We present a communication protocol for the erasure channel assisted by backward classical communication, which achieves a significantly better rate than the best prior result. In…
Breaking and making quantum money: toward a new quantum cryptographic protocol
Andrew Lutomirski, Scott Aaronson, Edward Farhi +4
Public-key quantum money is a cryptographic protocol in which a bank can create quantum states which anyone can verify but no one except possibly the bank can clone or forge. There…
The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
Edward Farhi, David Gosset, Itay Hen +4
In this paper we study the performance of the quantum adiabatic algorithm on random instances of two combinatorial optimization problems, 3-regular 3-XORSAT and 3-regular Max-Cut.…
Generalized Concatenated Quantum Codes
Markus Grassl, Peter Shor, Graeme Smith +2
We introduce the concept of generalized concatenated quantum codes. This generalized concatenation method provides a systematical way for constructing good quantum codes, both stab…
When is a bit worth much more than kT ln2?
Can Gokler, Artemy Kolchinsky, Zi-Wen Liu +6
Physical processes thatobtain, process, and erase information involve tradeoffs between information and energy. The fundamental energetic value of a bit of information exchanged wi…
A Discrete Fourier Transform on Lattices with Quantum Applications
Lior Eldar, Peter Shor
In this work, we introduce a definition of the Discrete Fourier Transform (DFT) on Euclidean lattices in , that generalizes the -th fold DFT of the integer lattice …
Different Strategies for Optimization Using the Quantum Adiabatic Algorithm
Elizabeth Crosson, Edward Farhi, Cedric Yen-Yu Lin +2
We present the results of a numerical study, with 20 qubits, of the performance of the Quantum Adiabatic Algorithm on randomly generated instances of MAX 2-SAT with a unique assign…
Efficiently Controllable Graphs
Can Gokler, Seth Lloyd, Peter Shor +1
We investigate graphs that can be disconnected into small components by removing a vanishingly small fraction of their vertices. We show that when a quantum network is described by…
The Quantum Transverse Field Ising Model on an Infinite Tree from Matrix Product States
Daniel Nagaj, Edward Farhi, Jeffrey Goldstone +2
We give a generalization to an infinite tree geometry of Vidal's infinite time-evolving block decimation (iTEBD) algorithm for simulating an infinite line of quantum spins. We nume…
Graph Concatenation for Quantum Codes
Salman Beigi, Isaac Chuang, Markus Grassl +2
Graphs are closely related to quantum error-correcting codes: every stabilizer code is locally equivalent to a graph code, and every codeword stabilized code can be described by a…
Quantum money from knots
Edward Farhi, David Gosset, Avinatan Hassidim +2
Quantum money is a cryptographic protocol in which a mint can produce a quantum state, no one else can copy the state, and anyone (with a quantum computer) can verify that the stat…
Unstructured Randomness, Small Gaps and Localization
Edward Farhi, Jeffrey Goldstone, David Gosset +2
We study the Hamiltonian associated with the quantum adiabatic algorithm with a random cost function. Because the cost function lacks structure we can prove results about the groun…
Maximizing free energy gain
Artemy Kolchinsky, Iman Marvian, Can Gokler +6
Maximizing the amount of work harvested from an environment is important for a wide variety of biological and technological processes, from energy-harvesting processes such as phot…
New Constructions of Codes for Asymmetric Channels via Concatenation
Markus Grassl, Peter Shor, Graeme Smith +2
We present new constructions of codes for asymmetric channels for both binary and nonbinary alphabets, based on methods of generalized code concatenation. For the binary asymmetric…
Quantum MacWilliams Identities
Peter Shor, Raymond Laflamme
We derive a relationship between two different notions of fidelity (entanglement fidelity and average fidelity) for a completely depolarizing quantum channel. This relationship giv…
Random Domino Tilings and the Arctic Circle Theorem
William Jockusch, James Propp, Peter Shor
In this article we study domino tilings of a family of finite regions called Aztec diamonds. Every such tiling determines a partition of the Aztec diamond into five sub-regions; in…
Criticality without frustration for quantum spin-1 chains
Sergey Bravyi, Libor Caha, Ramis Movassagh +2
Frustration-free (FF) spin chains have a property that their ground state minimizes all individual terms in the chain Hamiltonian. We ask how entangled the ground state of a FF qua…
Simultaneous Measurement and Entanglement
Andrey Boris Khesin, Peter Shor
We study scenarios which arise when two spatially-separated observers, Alice and Bob, are try to identify a quantum state sampled from several possibilities. In particular, we exam…
Quantum and Super-quantum enhancements to two-sender, two-receiver channels
Yihui Quek, Peter Shor
We study the consequences of 'super-quantum non-local correlations' as represented by the PR-box model of Popescu and Rohrlich, and show PR-boxes can enhance the capacity of noisy…