36 research outputs found
Approximating Output Probabilities of Shallow Quantum Circuits Which Are Geometrically-Local in Any Fixed Dimension
No full textWe present a classical algorithm that, for any D-dimensional geometrically-local, quantum circuit C of polylogarithmic-depth, and any bit string x ∈ {0,1}ⁿ, can compute the quantity ||² to within any inverse-polynomial additive error in quasi-polynomial time, for any fixed dimension D. This is an extension of the result [Nolan J. Coble and Matthew Coudron, 2021], which originally proved this result for D = 3. To see why this is interesting, note that, while the D = 1 case of this result follows from a standard use of Matrix Product States, known for decades, the D = 2 case required novel and interesting techniques introduced in [Sergy Bravyi et al., 2020]. Extending to the case D = 3 was even more laborious, and required further new techniques introduced in [Nolan J. Coble and Matthew Coudron, 2021]. Our work here shows that, while handling each new dimension has historically required a new insight, and fixed algorithmic primitive, based on known techniques for D ≤ 3, we can now handle any fixed dimension D > 3.
Our algorithm uses the Divide-and-Conquer framework of [Nolan J. Coble and Matthew Coudron, 2021] to approximate the desired quantity via several instantiations of the same problem type, each involving D-dimensional circuits on about half the number of qubits as the original. This division step is then applied recursively, until the width of the recursively decomposed circuits in the D^{th} dimension is so small that they can effectively be regarded as (D-1)-dimensional problems by absorbing the small width in the D^{th} dimension into the qudit structure at the cost of a moderate increase in runtime. The main technical challenge lies in ensuring that the more involved portions of the recursive circuit decomposition and error analysis from [Nolan J. Coble and Matthew Coudron, 2021] still hold in higher dimensions, which requires small modifications to the analysis in some places. Our work also includes some simplifications, corrections and clarifications of the use of block-encodings within the original classical algorithm in [Nolan J. Coble and Matthew Coudron, 2021]
Complexity Lower Bounds for Computing the Approximately-Commuting Operator Value of Non-Local Games to High Precision
No full textWe study the problem of approximating the commuting-operator value of a two-player non-local game. It is well-known that it is NP-complete to decide whether the classical value of a non-local game is 1 or 1- epsilon, promised that one of the two is the case. Furthermore, as long as epsilon is small enough, this result does not depend on the gap epsilon. In contrast, a recent result of Fitzsimons, Ji, Vidick, and Yuen shows that the complexity of computing the quantum value grows without bound as the gap epsilon decreases. In this paper, we show that this also holds for the commuting-operator value of a game. Specifically, in the language of multi-prover interactive proofs, we show that the power of MIP^{co}(2,1,1,s) (proofs with two provers, one round, completeness probability 1, soundness probability s, and commuting-operator strategies) can increase without bound as the gap 1-s gets arbitrarily small.
Our results also extend naturally in two ways, to perfect zero-knowledge protocols, and to lower bounds on the complexity of computing the approximately-commuting value of a game. Thus we get lower bounds on the complexity class PZK-MIP^{co}_{delta}(2,1,1,s) of perfect zero-knowledge multi-prover proofs with approximately-commuting operator strategies, as the gap 1-s gets arbitrarily small. While we do not know any computable time upper bound on the class MIP^{co}, a result of the first author and Vidick shows that for s = 1-1/poly(f(n)) and delta = 1/poly(f(n)), the class MIP^{co}_delta(2,1,1,s), with constant communication from the provers, is contained in TIME(exp(poly(f(n)))). We give a lower bound of coNTIME(f(n)) (ignoring constants inside the function) for this class, which is tight up to polynomial factors assuming the exponential time hypothesis
Universality of EPR Pairs in Entanglement-Assisted Communication Complexity, and the Communication Cost of State Conversion
No full textIn this work we consider the role of entanglement assistance in quantum communication protocols, focusing, in particular, on whether the type of shared entangled state can affect the quantum communication complexity of a function. This question is interesting because in some other settings in quantum information, such as non-local games, or tasks that involve quantum communication between players and referee, or simulating bipartite unitaries or communication channels, maximally entangled states are known to be less useful as a resource than some partially entangled states. By contrast, we prove that the bounded-error entanglement-assisted quantum communication complexity of a partial or total function cannot be improved by more than a constant factor by replacing maximally entangled states with arbitrary entangled states. In particular, we show that every quantum communication protocol using Q qubits of communication and arbitrary shared entanglement can be epsilon-approximated by a protocol using O(Q/epsilon+log(1/epsilon)/epsilon) qubits of communication and only EPR pairs as shared entanglement. This conclusion is opposite of the common wisdom in the study of non-local games, where it has been shown, for example, that the I3322 inequality has a non-local strategy using a non-maximally entangled state, which surpasses the winning probability achievable by any strategy using a maximally entangled state of any dimension [Vidick and Wehner, 2011]. We leave open the question of how much the use of a shared maximally entangled state can reduce the quantum communication complexity of a function.
Our second result concerns an old question in quantum information theory: How much quantum communication is required to approximately convert one pure bipartite entangled state into another? We give simple and efficiently computable upper and lower bounds. Given two bipartite states |chi> and |upsilon>, we define a natural quantity, d_{infty}(|chi>, |upsilon>), which we call the l_{infty} Earth Mover’s distance, and we show that the communication cost of converting between |chi> and |upsilon> is upper bounded by a constant multiple of d_{infty}(|chi>, |upsilon>). Here d_{infty}(|chi>, |upsilon>) may be informally described as the minimum over all transports between the log of the Schmidt coefficients of |chi> and those of |upsilon>, of the maximum distance that any amount of mass must be moved in that transport. A precise definition is given in the introduction. Furthermore, we prove a complementary lower bound on the cost of state conversion by the epsilon-Smoothed l_{infty}-Earth Mover’s Distance, which is a natural smoothing of the l_{infty}-Earth Mover’s Distance that we will define via a connection with optimal transport theory
Quantum algorithms and the power of forgetting
No full textThe so-called welded tree problem provides an example of a black-box problem
that can be solved exponentially faster by a quantum walk than by any classical
algorithm. Given the name of a special ENTRANCE vertex, a quantum walk can find
another distinguished EXIT vertex using polynomially many queries, though
without finding any particular path from ENTRANCE to EXIT. It has been an open
problem for twenty years whether there is an efficient quantum algorithm for
finding such a path, or if the path-finding problem is hard even for quantum
computers. We show that a natural class of efficient quantum algorithms
provably cannot find a path from ENTRANCE to EXIT. Specifically, we consider
algorithms that, within each branch of their superposition, always store a set
of vertex labels that form a connected subgraph including the ENTRANCE, and
that only provide these vertex labels as inputs to the oracle. While this does
not rule out the possibility of a quantum algorithm that efficiently finds a
path, it is unclear how an algorithm could benefit by deviating from this
behavior. Our no-go result suggests that, for some problems, quantum algorithms
must necessarily forget the path they take to reach a solution in order to
outperform classical computation.Comment: 49 pages, 9 figure
Local Hamiltonians with No Low-Energy Stabilizer States
No full textThe recently-defined No Low-energy Sampleable States (NLSS) conjecture of Gharibian and Le Gall [Sevag Gharibian and François {Le Gall}, 2022] posits the existence of a family of local Hamiltonians where all states of low-enough constant energy do not have succinct representations allowing perfect sampling access. States that can be prepared using only Clifford gates (i.e. stabilizer states) are an example of sampleable states, so the NLSS conjecture implies the existence of local Hamiltonians whose low-energy space contains no stabilizer states. We describe families that exhibit this requisite property via a simple alteration to local Hamiltonians corresponding to CSS codes. Our method can also be applied to the recent NLTS Hamiltonians of Anshu, Breuckmann, and Nirkhe [Anshu et al., 2022], resulting in a family of local Hamiltonians whose low-energy space contains neither stabilizer states nor trivial states. We hope that our techniques will eventually be helpful for constructing Hamiltonians which simultaneously satisfy NLSS and NLTS
Trading isolation for certifiable randomness expansion
No full textThesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013.Cataloged from PDF version of thesis.Includes bibliographical references (page 41).A source of random bits is an important resource in modern cryptography, algorithms and statistics. Can one ever be sure that a "random" source is truly random, or in the case of cryptography, secure against potential adversaries or eavesdroppers? Recently the study of non-local properties of entanglement has produced an interesting new perspective on this question, which we will refer to broadly as Certifiable Randomness Expansion (CRE). CRE refers generally to a process by which a source of information-theoretically certified randomness can be constructed based only on two simple assumptions: the prior existence of a short random seed and the ability to ensure that two or more black-box devices do not communicate (i.e. are non-signaling). In this work we make progress on a conjecture of [Col09] which proposes a method for indefinite certifiable randomness expansion using a growing number of devices (we actually prove a slight modification of the original conjecture in which we use the CHSH game as a subroutine rather than the GHZ game as originally proposed). The proof requires a technique not used before in the study of randomness expansion, and inspired by the tools developed in [RUV12]. The result also establishes the existence of a protocol for constant factor CRE using a finite number of devices (here the constant factor can be much greater than 1). While much better expansion rates (polynomial, and even exponential) have been achieved with only two devices, our analysis requires techniques not used before in the study of randomness expansion, and represents progress towards a protocol which is provably secure against a quantum eavesdropper who knows the input to the protocol.by Matthew Ryan Coudron.S.M
Entangled protocols and non-local games for testing quantum systems.
No full textThesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2017.Cataloged from PDF version of thesis.Includes bibliographical references (pages 177-184).The field of quantum computing investigates the extent to which one can design a quantum system that outperforms all known classical hardware at a certain task. But, to what extent can a human being, capable only (perhaps) of classical computation and of observing classical bit-string messages, verify that a quantum device in their possession is performing the task that they wish? This is a fundamental question about the nature of quantum mechanics, and the extent to which humans can harness it in a trustworthy manner. It is also a natural and important consideration when quantum devices may be used to perform sensitive cryptographic tasks which have no known efficient classical witness of correctness (Quantum Key Distribution, and Randomness Expansion are two examples of such tasks). It is remarkable that any quantum behavior at all can be tested by a verifier under such a constraint, without trusting any other quantum mechanical device in the process! But, intriguingly, when there are two or more quantum provers available in an interactive proof, there exist protocols to verify many interesting and useful quantum tasks in this setting. This thesis investigates multi-prover interactive proofs for verifying quantum behavior, and focuses on the stringent testing scenario in which the verifier in the interactive proof is completely classical as described above. It resolves the question of the maximum attainable expansion rate of a randomness expansion protocol by providing an adaptive randomness expansion protocol that achieves an arbitrary, or infinite rate of randomness expansion [29]. Secondly it presents a new rigidity result for the parallel repeated magic square game [24], which provides some improvements on previous rigidity results that play a pivotal role in existing interactive proofs for entangled provers, QKD, and randomness expansion results. This new rigidity result may be useful for improving such interactive proofs in the future. The second half of this thesis investigates the problem of bounding the role of quantum entanglement in non-local processes. This is important for understanding the upper limit on the power of multi-prover interactive proof systems with entangled provers. In particular it establishes that, assuming the Strong Kirchberg Conjecture, one can provide a doubly exponential upper bound on the class MIP* [25] (for comparison, the best known unconditional upper bound on MIP* is that its languages are recursively enumerable!). Finally this thesis presents a result which characterizes the type of entanglement that is useful in entanglement assisted quantum communication complexity by showing that any communication protocol using arbitrary shared entanglement can be simulated by a protocol using only EPR pairs for shared entanglement. Therefore all quantum communication protocols can be approximately simulated by a protocol using only the maximally entangled state as a shared resource.by Matthew Ryan Coudron.Ph. D
Interactive Proofs with Approximately Commuting Provers
No full textThe class MIP∗ of promise problems that can be decided through an interactive proof system with multiple entangled provers provides a complexity-theoretic framework for the exploration of the nonlocal properties of entanglement. Very little is known in terms of the power of this class. The only proposed approach for establishing upper bounds is based on a hierarchy of semidefinite programs introduced independently by Pironio et al. and Doherty et al. in 2006. This hierarchy converges to a value, the field-theoretic value, that is only known to coincide with the provers’ maximum success probability in a given proof system under a plausible but difficult mathematical conjecture, Connes’ embedding conjecture. No bounds on the rate of convergence are known.
We introduce a rounding scheme for the hierarchy, establishing that any solution to its N -th level can be mapped to a strategy for the provers in which measurement operators associated with distinct provers have pairwise commutator bounded by O(ℓ^2/√N) in operator norm, where ℓ is the number of possible answers per prover.
Our rounding scheme motivates the introduction of a variant of quantum multiprover interactive proof systems, called MIP∗_δ in which the soundness property is required to hold against provers allowed to operate on the same Hilbert space as long as the commutator of operations performed by distinct provers has norm at most δ. Our rounding scheme implies the upper bound MIP∗_δ ⊆ DTIME(exp(exp(poly)/δ^2)). In terms of lower bounds we establish that MIP∗_(2−poly) contains NEXP with completeness 1 and soundness 1−2^(−poly). We discuss connections with the mathematical literature on approximate commutation and applications to device-independent cryptography
Computations with greater Quantum depth are strictly more powerful (relative to an oracle)
No full text
