BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Peter Shor

Peter Shor appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
quant-phcond-mat.stat-mechComputational Complexitycond-mat.str-elCryptography and SecurityInformation Theorymath.IT

Catalog footprint

What is connected

13works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

13 published item(s)

preprint2022arXiv

Simultaneous Measurement and Entanglement

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 examine their strategies for maximizing both the probability of guessing their state correctly as well as their information gain about it. It is known that there are scenarios where allowing Alice and Bob to use LOCC offers an improvement over the case where they must make their measurements simultaneously. Similarly, Alice and Bob can sometimes improve their outcomes if they have access to a Bell pair. We show how LOCC allows Alice and Bob to distinguish between two product states optimally and find that a LOCC is almost always more helpful than a Bell pair for distinguishing product states.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Time Independent Universal Computing with Spin Chains: Quantum Plinko Machine

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 other to perform universal quantum computation. A circuit using g gate blocks on m qubits can be encoded into chains of length $O(g^{3+δ} m^{3+δ})$ for all $δ>0$ with vanishingly small error.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Different Strategies for Optimization Using the Quantum Adiabatic Algorithm

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 assignment that maximizes the number of satisfied clauses. The probability of obtaining this assignment at the end of the quantum evolution measures the success of the algorithm. Here we report three strategies which consistently increase the success probability for the hardest instances in our ensemble: decreasing the overall evolution time, initializing the system in excited states, and adding a random local Hamiltonian to the middle of the evolution.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

New Constructions of Codes for Asymmetric Channels via Concatenation

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 channel, our methods construct nonlinear single-error-correcting codes from ternary outer codes. We show that some of the Varshamov-Tenengol'ts-Constantin-Rao codes, a class of binary nonlinear codes for this channel, have a nice structure when viewed as ternary codes. In many cases, our ternary construction yields even better codes. For the nonbinary asymmetric channel, our methods construct linear codes for many lengths and distances which are superior to the linear codes of the same length capable of correcting the same number of symmetric errors. In the binary case, Varshamov has shown that almost all good linear codes for the asymmetric channel are also good for the symmetric channel. Our results indicate that Varshamov's argument does not extend to the nonbinary case, i.e., one can find better linear codes for asymmetric channels than for symmetric ones.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Criticality without frustration for quantum spin-1 chains

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 quantum spin-s chain with nearest-neighbor interactions can be for small values of s. While FF spin-1/2 chains are known to have unentangled ground states, the case s=1 remains less explored. We propose the first example of a FF translation-invariant spin-1 chain that has a unique highly entangled ground state and exhibits some signatures of a critical behavior. The ground state can be viewed as the uniform superposition of balanced strings of left and right parentheses separated by empty spaces. Entanglement entropy of one half of the chain scales as log(n)/2 + O(1), where n is the number of spins. We prove that the energy gap above the ground state is polynomial in 1/n. The proof relies on a new result concerning statistics of Dyck paths which might be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs

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. The cost functions associated with these two clause-based optimization problems are similar as they are both defined on 3-regular hypergraphs. For 3-regular 3-XORSAT the clauses contain three variables and for 3-regular Max-Cut the clauses contain two variables. The quantum adiabatic algorithms we study for these two problems use interpolating Hamiltonians which are stoquastic and therefore amenable to sign-problem free quantum Monte Carlo and quantum cavity methods. Using these techniques we find that the quantum adiabatic algorithm fails to solve either of these problems efficiently, although for different reasons.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Quantum state restoration and single-copy tomography

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 procedure which verifies the state, for example a procedure which measures the operator |psi><psi|, we cannot prepare |psi> in time polynomial in n . In this paper, we consider the scenario in which we are given both a single copy of |psi> and the ability to verify it. We show that in this setting, we can do several novel things efficiently. We present a new algorithm that we call quantum state restoration which allows us to extend a large subsystem of |psi> to the full state, and in turn this allows us to copy small subsystems of |psi>. In addition, we present algorithms that can perform tomography on small subsystems of |psi>, and we show how to use these algorithms to estimate the statistics of any efficiently implementable POVM acting on |psi> in time polynomial in the number of outcomes of the POVM.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Graph Concatenation for Quantum Codes

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 graph and a classical code. For the construction of good quantum codes of relatively large block length, concatenated quantum codes and their generalizations play an important role. We develop a systematic method for constructing concatenated quantum codes based on "graph concatenation", where graphs representing the inner and outer codes are concatenated via a simple graph operation called "generalized local complementation." Our method applies to both binary and non-binary concatenated quantum codes as well as their generalizations.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On quantum capacity of erasure channel assisted by back classical communication

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 addition, we prove an upper bound for the capacity of the channel. The upper bound is smaller than the capacity of the erasure channel when it is assisted by two-way classical communication. Thus, we prove the separation between quantum capacities assisted by backward classical communication and two-way classical communication.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Quantum Adiabatic Algorithms, Small Gaps, and Different Paths

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 consistent with two disparate planted solutions and then penalizing one of them with a single additional clause. We argue that by randomly modifying the beginning Hamiltonian, one obtains (with substantial probability) an adiabatic path that removes this difficulty. This suggests that the quantum adiabatic algorithm should in general be run on each instance with many different random paths leading to the problem Hamiltonian. We do not know whether this trick will help for a random instance of 3SAT (as opposed to an instance from the particular set we consider), especially if the instance has an exponential number of disparate assignments that violate few clauses. We use a continuous imaginary time Quantum Monte Carlo algorithm in a novel way to numerically investigate the ground state as well as the first excited state of our system. Our arguments are supplemented by Quantum Monte Carlo data from simulations with up to 150 spins.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Quantum money from knots

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 state came from the mint. We present a concrete quantum money scheme based on superpositions of diagrams that encode oriented links with the same Alexander polynomial. We expect our scheme to be secure against computationally bounded adversaries.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Unstructured Randomness, Small Gaps and Localization

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 ground state. We find the ground state energy as the number of bits goes to infinity, show that the minimum gap goes to zero exponentially quickly, and we see a localization transition. We prove that there are no levels approaching the ground state near the end of the evolution. We do not know which features of this model are shared by a quantum adiabatic algorithm applied to random instances of satisfiability since despite being random they do have bit structure.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Breaking and making quantum money: toward a new quantum cryptographic protocol

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 are no secure public-key quantum money schemes in the literature; as we show in this paper, the only previously published scheme [1] is insecure. We introduce a category of quantum money protocols which we call collision-free. For these protocols, even the bank cannot prepare multiple identical-looking pieces of quantum money. We present a blueprint for how such a protocol might work as well as a concrete example which we believe may be insecure.

0 citations0 reviewsNo code linkedOpen access