An official website of the United States government
We propose a set of Bell-type nonlocal games that can be used to prove an unconditional quantum advantage in an objective and hardware-agnostic manner. In these games, the circuit depth needed to prepare a cyclic cluster state and measure a subset of its Pauli stabilizers on a quantum computer is compared to that of classical Boolean circuits with the same, nearest-neighboring gate connectivity. Using a circuit-based trapped-ion quantum computer, we prepare and measure a six-qubit cyclic cluster state with an overall fidelity of 60.6% and 66.4%, before and after correcting for measurement-readout errors, respectively. Our experimental results indicate that while this fidelity readily passes conventional (or depth-0) Bell bounds for local hidden-variable models, it is on the cusp of demonstrating a higher probability of success than what is possible by depth-1 classical circuits. Our games offer a practical and scalable set of quantitative benchmarks for quantum computers in the pre-fault-tolerant regime as the number of qubits available increases.
more »
« less
Quantum Computational Advantage with String Order Parameters of One-Dimensional Symmetry-Protected Topological Order
Nonlocal games with advantageous quantum strategies give arguably the most fundamental demonstration of the power of quantum resources over their classical counterparts. Recently, certain multiplayer generalizations of nonlocal games have been used to prove unconditional separations between limited computational complexity classes of shallow-depth circuits. Here, we show advantageous strategies for these nonlocal games for generic ground states of one-dimensional symmetry-protected topological orders (SPTOs), when a discrete invariant of a SPTO known as a twist phase is nontrivial and -1. Our construction demonstrates that sufficiently large string order parameters of such SPTOs are indicative of globally constrained correlations useful for the unconditional computational separation.
more »
« less
- Award ID(s):
- 1915011
- PAR ID:
- 10288529
- Date Published:
- Journal Name:
- Physical review letters
- Volume:
- 126
- ISSN:
- 1079-7114
- Page Range / eLocation ID:
- 090505
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract We present a theoretical and computational framework based on fractional calculus for the analysis of the nonlocal static response of cylindrical shell panels. The differ-integral nature of fractional derivatives allows an efficient and accurate methodology to account for the effect of long-range (nonlocal) interactions in curved structures. More specifically, the use of frame-invariant fractional-order kinematic relations enables a physically, mathematically, and thermodynamically consistent formulation to model the nonlocal elastic interactions. To evaluate the response of these nonlocal shells under practical scenarios involving generalized loads and boundary conditions, the fractional-finite element method (f-FEM) is extended to incorporate shell elements based on the first-order shear-deformable displacement theory. Finally, numerical studies are performed exploring both the linear and the geometrically nonlinear static response of nonlocal cylindrical shell panels. This study is intended to provide a general foundation to investigate the nonlocal behavior of curved structures by means of fractional-order models.more » « less
-
Recent developments in domains such as non-local games, quantum interactive proofs, and quantum generative adversarial networks have renewed interest in quantum game theory and, specifically, quantum zero-sum games. Central to classical game theory is the efficient algorithmic computation of Nash equilibria, which represent optimal strategies for both players. In 2008, Jain and Watrous proposed the first classical algorithm for computing equilibria in quantum zerosum games using the Matrix Multiplicative Weight Updates (MMWU) method to achieve a convergence rate of O(d/ε2) iterations to ε-Nash equilibria in the 4d-dimensional spectraplex. In this work, we propose a hierarchy of quantum optimization algorithms that generalize MMWU via an extra-gradient mechanism. Notably, within this proposed hierarchy, we introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as O(d/ε) iterations to ε-Nash equilibria. This quadratic speed-up relative to Jain and Watrous’ original algorithm sets a new benchmark for computing ε-Nash equilibria in quantum zero-sum games.more » « less
-
We consider computational games, sequences of games G = (G1,G2,...) where, for all n, Gn has the same set of players. Computational games arise in electronic money systems such as Bitcoin, in cryptographic protocols, and in the study of generative adversarial networks in machine learning. Assuming that one-way functions exist, we prove that there is 2-player zero-sum computational game G such that, for all n, the size of the action space in Gn is polynomial in n and the utility function in Gn is computable in time polynomial in n, and yet there is no ε-Nash equilibrium if players are restricted to using strategies computable by polynomial-time Turing machines, where we use a notion of Nash equilibrium that is tailored to computational games. We also show that an ε-Nash equilibrium may not exist if players are constrained to perform at most T computational steps in each of the games in the sequence. On the other hand, we show that if players can use arbitrary Turing machines to compute their strategies, then every computational game has an ε-Nash equilibrium. These results may shed light on competitive settings where the availability of more running time or faster algorithms can lead to a “computational arms race”, precluding the existence of equilibrium. They also point to inherent limitations of concepts such as “best response” and Nash equilibrium in games with resource-bounded players.more » « less
-
Abstract In this work we initiate the study of position based quantum cryptography (PBQC) from the perspective of geometric functional analysis and its connections with quantum games. The main question we are interested in asks for the optimal amount of entanglement that a coalition of attackers have to share in order to compromise the security of any PBQC protocol. Known upper bounds for that quantity are exponential in the size of the quantum systems manipulated in the honest implementation of the protocol. However, known lower bounds are only linear. In order to deepen the understanding of this question, here we propose a position verification (PV) protocol and find lower bounds on the resources needed to break it. The main idea behind the proof of these bounds is the understanding of cheating strategies as vector valued assignments on the Boolean hypercube. Then, the bounds follow from the understanding of some geometric properties of particular Banach spaces, their type constants. Under some regularity assumptions on the former assignment, these bounds lead to exponential lower bounds on the quantum resources employed, clarifying the question in this restricted case. Known attacks indeed satisfy the assumption we make, although we do not know how universal this feature is. Furthermore, we show that the understanding of the type properties of some more involved Banach spaces would allow to drop out the assumptions and lead to unconditional lower bounds on the resources used to attack our protocol. Unfortunately, we were not able to estimate the relevant type constant. Despite that, we conjecture an upper bound for this quantity and show some evidence supporting it. A positive solution of the conjecture would lead to stronger security guarantees for the proposed PV protocol providing a better understanding of the question asked above.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/https://doi.org/10.1103/PhysRevLett.126.090505
