skip to main content


Title: Practically secure quantum position verification
Abstract We discuss quantum position verification (QPV) protocols in which the verifiers create and send single-qubit states to the prover. QPV protocols using single-qubit states are known to be insecure against adversaries that share a small number of entangled qubits. We introduce QPV protocols that are practically secure: they only require single-qubit states from each of the verifiers, yet their security is broken if the adversaries sharing an impractically large number of entangled qubits employ teleportation-based attacks. These protocols are a modification of known QPV protocols in which we include a classical random oracle without altering the amount of quantum resources needed by the verifiers. We present a cheating strategy that requires a number of entangled qubits shared among the adversaries that grows exponentially with the size of the classical input of the random oracle.  more » « less
Award ID(s):
1937008
NSF-PAR ID:
10316460
Author(s) / Creator(s):
;
Date Published:
Journal Name:
New Journal of Physics
Volume:
23
Issue:
6
ISSN:
1367-2630
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Cellular automata are interacting classical bits that display diverse behaviors, from fractals to random-number generators to Turing-complete computation. We introduce entangled quantum cellular automata subject to Goldilocks rules, tradeoffs of the kind underpinning biological, social, and economic complexity. Tweaking digital and analog quantum-computing protocols generates persistent entropy fluctuations; robust dynamical features, including an entangled breather; and network structure and dynamics consistent with complexity. Present-day quantum platforms---Rydberg arrays, trapped ions, and superconducting qubits---can implement Goldilocks protocols, which generate quantum many-body states with rich entanglement and structure. Moreover, the complexity studies reported here underscore an emerging idea in many-body quantum physics: some systems fall outside the integrable/chaotic dichotomy. 
    more » « less
  2. Abstract The ability to engineer parallel, programmable operations between desired qubits within a quantum processor is key for building scalable quantum information systems 1,2 . In most state-of-the-art approaches, qubits interact locally, constrained by the connectivity associated with their fixed spatial layout. Here we demonstrate a quantum processor with dynamic, non-local connectivity, in which entangled qubits are coherently transported in a highly parallel manner across two spatial dimensions, between layers of single- and two-qubit operations. Our approach makes use of neutral atom arrays trapped and transported by optical tweezers; hyperfine states are used for robust quantum information storage, and excitation into Rydberg states is used for entanglement generation 3–5 . We use this architecture to realize programmable generation of entangled graph states, such as cluster states and a seven-qubit Steane code state 6,7 . Furthermore, we shuttle entangled ancilla arrays to realize a surface code state with thirteen data and six ancillary qubits 8 and a toric code state on a torus with sixteen data and eight ancillary qubits 9 . Finally, we use this architecture to realize a hybrid analogue–digital evolution 2 and use it for measuring entanglement entropy in quantum simulations 10–12 , experimentally observing non-monotonic entanglement dynamics associated with quantum many-body scars 13,14 . Realizing a long-standing goal, these results provide a route towards scalable quantum processing and enable applications ranging from simulation to metrology. 
    more » « less
  3. We consider the problem of efficiently simulating random quantum states and random unitary operators, in a manner which is convincing to unbounded adversaries with black-box oracle access. This problem has previously only been considered for restricted adversaries. Against adversaries with an a priori bound on the number of queries, it is well-known that t-designs suffice. Against polynomial-time adversaries, one can use pseudorandom states (PRS) and pseudorandom unitaries (PRU), as defined in a recent work of Ji, Liu, and Song; unfortunately, no provably secure construction is known for PRUs. In our setting, we are concerned with unbounded adversaries. Nonetheless, we are able to give stateful quantum algorithms which simulate the ideal object in both settings of interest. In the case of Haar-random states, our simulator is polynomial-time, has negligible error, and can also simulate verification and reflection through the simulated state. This yields an immediate application to quantum money: a money scheme which is information-theoretically unforgeable and untraceable. In the case of Haar-random unitaries, our simulator takes polynomial space, but simulates both forward and inverse access with zero error. These results can be seen as the first significant steps in developing a theory of lazy sampling for random quantum objects. 
    more » « less
  4. Recent constructions of quantum low-density parity-check (QLDPC) codes provide optimal scaling of the number of logical qubits and the minimum distance in terms of the code length, thereby opening the door to fault-tolerant quantum systems with minimal resource overhead. However, the hardware path from nearest-neighbor-connection-based topological codes to long-range-interaction-demanding QLDPC codes is likely a challenging one. Given the practical difficulty in building a monolithic architecture for quantum systems, such as computers, based on optimal QLDPC codes, it is worth considering a distributed implementation of such codes over a network of interconnected medium-sized quantum processors. In such a setting, all syndrome measurements and logical operations must be performed through the use of high-fidelity shared entangled states between the processing nodes. Since probabilistic many-to-1 distillation schemes for purifying entanglement are inefficient, we investigate quantum error correction based entanglement purification in this work. Specifically, we employ QLDPC codes to distill GHZ states, as the resulting high-fidelity logical GHZ states can interact directly with the code used to perform distributed quantum computing (DQC), e.g. for fault-tolerant Steane syndrome extraction. This protocol is applicable beyond the application of DQC since entanglement distribution and purification is a quintessential task of any quantum network. We use the min-sum algorithm (MSA) based iterative decoder with a sequential schedule for distilling3-qubit GHZ states using a rate0.118family of lifted product QLDPC codes and obtain an input fidelity threshold of0.7974under i.i.d. single-qubit depolarizing noise. This represents the best threshold for a yield of0.118for any GHZ purification protocol. Our results apply to larger size GHZ states as well, where we extend our technical result about a measurement property of3-qubit GHZ states to construct a scalable GHZ purification protocol.

     
    more » « less
  5. Using IBM's publicly accessible quantum computers, we have analyzed the entropies of Schrödinger's cat states, which have the form Ψ = (1/2) 1/2 [|0 0 0⋯0〉 + |1 1 1⋯1〉]. We have obtained the average Shannon entropy S So of the distribution over measurement outcomes from 75 runs of 8192 shots, for each of the numbers of entangled qubits, on each of the quantum computers tested. For the distribution over N fault-free measurements on pure cat states, S So would approach one as N → ∞, independent of the number of qubits; but we have found that S So varies nearly linearly with the number of qubits n . The slope of S So versus the number of qubits differs among computers with the same quantum volumes. We have developed a two-parameter model that reproduces the near-linear dependence of the entropy on the number of qubits, based on the probabilities of observing the output 0 when a qubit is set to |0〉 and 1 when it is set to |1〉. The slope increases as the error rate increases. The slope provides a sensitive measure of the accuracy of a quantum computer, so it serves as a quickly determinable index of performance. We have used tomographic methods with error mitigation as described in the qiskit documentation to find the density matrix ρ and evaluate the von Neumann entropies of the cat states. From the reduced density matrices for individual qubits, we have calculated the entanglement entropies. The reduced density matrices represent mixed states with approximately 50/50 probabilities for states |0〉 and |1〉. The entanglement entropies are very close to one. 
    more » « less