01544nas a2200145 4500008004100000245006100041210006000102260001300162520109800175100002101273700001901294700002501313700002301338856003701361 2020 eng d00aNearly optimal time-independent reversal of a spin chain0 aNearly optimal timeindependent reversal of a spin chain c3/5/20203 a

We propose a time-independent Hamiltonian protocol for the reversal of qubit ordering in a chain of N spins. Our protocol has an easily implementable nearest-neighbor, transverse-field Ising model Hamiltonian with time-independent, non-uniform couplings. Under appropriate normalization, we implement this state reversal three times faster than a naive approach using SWAP gates, in time comparable to a protocol of Raussendorf [Phys. Rev. A 72, 052301 (2005)] that requires dynamical control. We also prove lower bounds on state reversal by using results on the entanglement capacity of Hamiltonians and show that we are within a factor 1.502(1+1/N) of the shortest time possible. Our lower bound holds for all nearest-neighbor qubit protocols with arbitrary finite ancilla spaces and local operations and classical communication. Finally, we extend our protocol to an infinite family of nearest-neighbor, time-independent Hamiltonian protocols for state reversal. This includes chains with nearly uniform coupling that may be especially feasible for experimental implementation. 

1 aBapat, Aniruddha1 aSchoute, Eddie1 aGorshkov, Alexey, V.1 aChilds, Andrew, M. uhttps://arxiv.org/abs/2003.0284301889nas a2200169 4500008004100000245006600041210006500107260001300172300001200185490004400197520136000241100001901601700002301620700002001643700001901663856003701682 2020 eng d00aNon-interactive classical verification of quantum computation0 aNoninteractive classical verification of quantum computation c3/9/2020 a153-1800 vLecture Notes in Computer Science 125523 a

In a recent breakthrough, Mahadev constructed an interactive protocol that enables a purely classical party to delegate any quantum computation to an untrusted quantum prover. In this work, we show that this same task can in fact be performed non-interactively and in zero-knowledge.
Our protocols result from a sequence of significant improvements to the original four-message protocol of Mahadev. We begin by making the first message instance-independent and moving it to an offline setup phase. We then establish a parallel repetition theorem for the resulting three-message protocol, with an asymptotically optimal rate. This, in turn, enables an application of the Fiat-Shamir heuristic, eliminating the second message and giving a non-interactive protocol. Finally, we employ classical non-interactive zero-knowledge (NIZK) arguments and classical fully homomorphic encryption (FHE) to give a zero-knowledge variant of this construction. This yields the first purely classical NIZK argument system for QMA, a quantum analogue of NP.
We establish the security of our protocols under standard assumptions in quantum-secure cryptography. Specifically, our protocols are secure in the Quantum Random Oracle Model, under the assumption that Learning with Errors is quantumly hard. The NIZK construction also requires circuit-private FHE.

1 aAlagic, Gorjan1 aChilds, Andrew, M.1 aGrilo, Alex, B.1 aHung, Shih-Han uhttps://arxiv.org/abs/1911.0810101490nas a2200133 4500008004100000245005800041210005800099260001500157490000800172520110300180100002301283700001301306856003701319 2019 eng d00aNearly optimal lattice simulation by product formulas0 aNearly optimal lattice simulation by product formulas c12/17/20190 v1233 a

Product formulas provide a straightforward yet surprisingly efficient approach to quantum simulation. We show that this algorithm can simulate an n-qubit Hamiltonian with nearest-neighbor interactions evolving for time t using only (nt)1+o(1) gates. While it is reasonable to expect this complexity---in particular, this was claimed without rigorous justification by Jordan, Lee, and Preskill---we are not aware of a straightforward proof. Our approach is based on an analysis of the local error structure of product formulas, as introduced by Descombes and Thalhammer and significantly simplified here. We prove error bounds for canonical product formulas, which include well-known constructions such as the Lie-Trotter-Suzuki formulas. We also develop a local error representation for time-dependent Hamiltonian simulation, and we discuss generalizations to periodic boundary conditions, constant-range interactions, and higher dimensions. Combined with a previous lower bound, our result implies that product formulas can simulate lattice Hamiltonians with nearly optimal gate complexity.

1 aChilds, Andrew, M.1 aSu, Yuan uhttps://arxiv.org/abs/1901.00564