01436nas a2200133 4500008004100000245007900041210006900120260001400189520100200203100002001205700002101225700001901246856003701265 2024 eng d00aBeatty Sequences for a Quadratic Irrational: Decidability and Applications0 aBeatty Sequences for a Quadratic Irrational Decidability and App c2/13/20243 a

Let α and β belong to the same quadratic field. We show that the inhomogeneous Beatty sequence (⌊nα+β⌋)n≥1 is synchronized, in the sense that there is a finite automaton that takes as input the Ostrowski representations of n and y in parallel, and accepts if and only if y=⌊nα+β⌋. Since it is already known that the addition relation is computable for Ostrowski representations based on a quadratic number, a consequence is a new and rather simple proof that the first-order logical theory of these sequences with addition is decidable. The decision procedure is easily implemented in the free software Walnut.  As an application, we show that for each r≥1 it is decidable whether the set {⌊nα+β⌋:n≥1} forms an additive basis (or asymptotic additive basis) of order r. Using our techniques, we also solve some open problems of Reble and Kimberling, and give an explicit characterization of a sequence of Hildebrand et al.

1 aSchaeffer, Luke1 aShallit, Jeffrey1 aZorcic, Stefan uhttps://arxiv.org/abs/2402.0833101453nas a2200121 4500008004100000245004000041210004000081260001400121520111400135100002401249700002101273856003701294 2023 eng d00aBell sampling from quantum circuits0 aBell sampling from quantum circuits c10/6/20233 a

A central challenge in the verification of quantum computers is benchmarking their performance as a whole and demonstrating their computational capabilities. In this work, we find a universal model of quantum computation, Bell sampling, that can be used for both of those tasks and thus provides an ideal stepping stone towards fault-tolerance. In Bell sampling, we measure two copies of a state prepared by a quantum circuit in the transversal Bell basis. We show that the Bell samples are classically intractable to produce and at the same time constitute what we call a circuit shadow: from the Bell samples we can efficiently extract information about the quantum circuit preparing the state, as well as diagnose circuit errors. In addition to known properties that can be efficiently extracted from Bell samples, we give two new and efficient protocols, a test for the depth of the circuit and an algorithm to estimate a lower bound to the number of T gates in the circuit. With some additional measurements, our algorithm learns a full description of states prepared by circuits with low T-count.

1 aHangleiter, Dominik1 aGullans, Michael uhttps://arxiv.org/abs/2306.0008301443nas a2200121 4500008004100000245004000041210004000081260001400121520110400135100002401239700002101263856003701284 2023 eng d00aBell sampling from quantum circuits0 aBell sampling from quantum circuits c6/19/20233 a

A central challenge in the verification of quantum computers is benchmarking their performance as a whole and demonstrating their computational capabilities. In this work, we find a model of quantum computation, Bell sampling, that can be used for both of those tasks and thus provides an ideal stepping stone towards fault-tolerance. In Bell sampling, we measure two copies of a state prepared by a quantum circuit in the transversal Bell basis. We show that the Bell samples are classically intractable to produce and at the same time constitute what we call a circuit shadow: from the Bell samples we can efficiently extract information about the quantum circuit preparing the state, as well as diagnose circuit errors. In addition to known properties that can be efficiently extracted from Bell samples, we give two new and efficient protocols, a test for the depth of the circuit and an algorithm to estimate a lower bound to the number of T gates in the circuit. With some additional measurements, our algorithm learns a full description of states prepared by circuits with low T-count.

1 aHangleiter, Dominik1 aGullans, Michael uhttps://arxiv.org/abs/2306.0008301560nas a2200157 4500008004100000245005000041210005000091260001400141520111200155100001801267700001601285700001601301700002501317700002301342856003701365 2023 eng d00aBounds on Autonomous Quantum Error Correction0 aBounds on Autonomous Quantum Error Correction c8/30/20233 a

Autonomous quantum memories are a way to passively protect quantum information using engineered dissipation that creates an "always-on'' decoder. We analyze Markovian autonomous decoders that can be implemented with a wide range of qubit and bosonic error-correcting codes, and derive several upper bounds and a lower bound on the logical error rate in terms of correction and noise rates. For many-body quantum codes, we show that, to achieve error suppression comparable to active error correction, autonomous decoders generally require correction rates that grow with code size. For codes with a threshold, we show that it is possible to achieve faster-than-polynomial decay of the logical error rate with code size by using superlogarithmic scaling of the correction rate. We illustrate our results with several examples. One example is an exactly solvable global dissipative toric code model that can achieve an effective logical error rate that decreases exponentially with the linear lattice size, provided that the recovery rate grows proportionally with the linear lattice size.

1 aShtanko, Oles1 aLiu, Yu-Jie1 aLieu, Simon1 aGorshkov, Alexey, V.1 aAlbert, Victor, V. uhttps://arxiv.org/abs/2308.1623301081nas a2200157 4500008004100000245004200041210004200083260001300125520065300138100001600791700001400807700002400821700002000845700002100865856003700886 2022 eng d00aBoson Sampling for Generalized Bosons0 aBoson Sampling for Generalized Bosons c5/2/20223 a

We introduce the notion of "generalized bosons" whose exchange statistics resemble those of bosons, but the local bosonic commutator [ai,a†i]=1 is replaced by an arbitrary single-mode operator that is diagonal in the generalized Fock basis. Examples of generalized bosons include boson pairs and spins. We consider the analogue of the boson sampling task for these particles and observe that its output probabilities are still given by permanents, so that the results regarding hardness of sampling directly carry over. Finally, we propose implementations of generalized boson sampling in circuit-QED and ion-trap platforms.

1 aKuo, En-Jui1 aXu, Yijia1 aHangleiter, Dominik1 aGrankin, Andrey1 aHafezi, Mohammad uhttps://arxiv.org/abs/2204.0838900958nas a2200157 4500008004100000245004700041210004600088260001500134520045900149653004300608653002700651653003100678653003100709100002300740856003700763 2022 eng d00aBosonic coding: introduction and use cases0 aBosonic coding introduction and use cases c11/10/20223 a

Bosonic or continuous-variable coding is a field concerned with robust quantum information processing and communication with electromagnetic signals or mechanical modes. I review bosonic quantum memories, characterizing them as either bosonic stabilizer or bosonic Fock-state codes. I then enumerate various applications of bosonic encodings, four of which circumvent no-go theorems due to the intrinsic infinite-dimensionality of bosonic systems.

10aFOS: Computer and information sciences10aFOS: Physical sciences10aInformation Theory (cs.IT)10aQuantum Physics (quant-ph)1 aAlbert, Victor, V. uhttps://arxiv.org/abs/2211.0571402469nas a2200217 4500008004100000245001900041210001900060260001400079520185900093653003401952653004301986653002702029653003102056100002602087700001902113700001702132700002502149700002202174700001802196856003702214 2022 eng d00aBosonic Qiskit0 aBosonic Qiskit c9/22/20223 a

The practical benefits of hybrid quantum information processing hardware that contains continuous-variable objects (bosonic modes such as mechanical or electromagnetic oscillators) in addition to traditional (discrete-variable) qubits have recently been demonstrated by experiments with bosonic codes that reach the break-even point for quantum error correction and by efficient Gaussian boson sampling simulation of the Franck-Condon spectra of triatomic molecules that is well beyond the capabilities of current qubit-only hardware. The goal of this Co-design Center for Quantum Advantage (C2QA) project is to develop an instruction set architecture (ISA) for hybrid qubit/bosonic mode systems that contains an inventory of the fundamental operations and measurements that are possible in such hardware. The corresponding abstract machine model (AMM) would also contain a description of the appropriate error models associated with the gates, measurements and time evolution of the hardware. This information has been implemented as an extension of Qiskit. Qiskit is an opensource software development toolkit (SDK) for simulating the quantum state of a quantum circuit on a system with Python 3.7+ and for running the same circuits on prototype hardware within the IBM Quantum Lab. We introduce the Bosonic Qiskit software to enable the simulation of hybrid qubit/bosonic systems using the existing Qiskit software development kit. This implementation can be used for simulating new hybrid systems, verifying proposed physical systems, and modeling systems larger than can currently be constructed. We also cover tutorials and example use cases included within the software to study Jaynes- Cummings models, bosonic Hubbard models, plotting Wigner functions and animations, and calculating maximum likelihood estimations using Wigner functions.

10aEmerging Technologies (cs.ET)10aFOS: Computer and information sciences10aFOS: Physical sciences10aQuantum Physics (quant-ph)1 aStavenger, Timothy, J1 aCrane, Eleanor1 aSmith, Kevin1 aKang, Christopher, T1 aGirvin, Steven, M1 aWiebe, Nathan uhttps://arxiv.org/abs/2209.1115301277nas a2200157 4500008004100000245005500041210005500096260001400151520078300165653002700948653003100975100002101006700002301027700003201050856003701082 2022 eng d00aBounding the Minimum Time of a Quantum Measurement0 aBounding the Minimum Time of a Quantum Measurement c9/13/20223 a

Measurements take a singular role in quantum theory. While they are often idealized as an instantaneous process, this is in conflict with all other physical processes in nature. In this Letter, we adopt a standpoint where the interaction with an environment is a crucial ingredient for the occurrence of a measurement. Within this framework, we derive lower bounds on the time needed for a measurement to occur. Our bound scales proportionally to the change in entropy of the measured system, and inversely proportional to the number of possible measurement outcomes and the interaction strength driving the measurement. We evaluate our bound in two examples where the environment is modelled by bosonic modes and the measurement apparatus is modelled by spins or bosons.

10aFOS: Physical sciences10aQuantum Physics (quant-ph)1 aShettell, Nathan1 aCentrone, Federico1 aGarcía-Pintos, Luis, Pedro uhttps://arxiv.org/abs/2209.0624802137nas a2200169 4500008004100000245004200041210004200083260001300125520166200138100002101800700001701821700002401838700002101862700002201883700002501905856003701930 2021 eng d00aBehavior of Analog Quantum Algorithms0 aBehavior of Analog Quantum Algorithms c7/2/20213 a

Analog quantum algorithms are formulated in terms of Hamiltonians rather than unitary gates and include quantum adiabatic computing, quantum annealing, and the quantum approximate optimization algorithm (QAOA). These algorithms are promising candidates for near-term quantum applications, but they often require fine tuning via the annealing schedule or variational parameters. In this work, we explore connections between these analog algorithms, as well as limits in which they become approximations of the optimal procedure.Notably, we explore how the optimal procedure approaches a smooth adiabatic procedure but with a superposed oscillatory pattern that can be explained in terms of the interactions between the ground state and first excited state that effect the coherent error cancellation of diabatic transitions. Furthermore, we provide numeric and analytic evidence that QAOA emulates this optimal procedure with the length of each QAOA layer equal to the period of the oscillatory pattern. Additionally, the ratios of the QAOA bangs are determined by the smooth, non-oscillatory part of the optimal procedure. We provide arguments for these phenomena in terms of the product formula expansion of the optimal procedure. With these arguments, we conclude that different analog algorithms can emulate the optimal protocol under different limits and approximations. Finally, we present a new algorithm for better approximating the optimal protocol using the analytic and numeric insights from the rest of the paper. In practice, numerically, we find that this algorithm outperforms standard QAOA and naive quantum annealing procedures. 

1 aBrady, Lucas, T.1 aKocia, Lucas1 aBienias, Przemyslaw1 aBapat, Aniruddha1 aKharkov, Yaroslav1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/2107.0121801337nas a2200157 4500008004100000245007600041210006900117260001400186490000800200520085400208100001901062700001901081700001901100700001901119856004101138 2020 eng d00aBack-action evading impulse measurement with mechanical quantum sensors0 aBackaction evading impulse measurement with mechanical quantum s c8/28/20200 v1023 a

The quantum measurement of any observable naturally leads to noise added by the act of measurement. Approaches to evade or reduce this noise can lead to substantial improvements in a wide variety of sensors, from laser interferometers to precision magnetometers and more. In this paper, we develop a measurement protocol based upon pioneering work by the gravitational wave community which allows for reduction of added noise from measurement by coupling an optical field to the momentum of a small mirror. As a specific implementation, we present a continuous measurement protocol using a double-ring optomechanical cavity. We demonstrate that with experimentally-relevant parameters, this protocol can lead to significant back-action noise evasion, yielding measurement noise below the standard quantum limit over many decades of frequency.

1 aGhosh, Sohitri1 aCarney, Daniel1 aShawhan, Peter1 aTaylor, J., M. uhttps://arxiv.org/pdf/1910.11892.pdf02079nas a2200133 4500008004100000245007500041210006900116260001400185520165000199100001801849700001901867700002201886856003701908 2020 eng d00aA Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds0 aBlackBox Approach to PostQuantum ZeroKnowledge in Constant Round c11/5/20203 a

In a recent seminal work, Bitansky and Shmueli (STOC '20) gave the first construction of a constant round zero-knowledge argument for NP secure against quantum attacks. However, their construction has several drawbacks compared to the classical counterparts. Specifically, their construction only achieves computational soundness, requires strong assumptions of quantum hardness of learning with errors (QLWE assumption) and the existence of quantum fully homomorphic encryption (QFHE), and relies on non-black-box simulation. In this paper, we resolve these issues at the cost of weakening the notion of zero-knowledge to what is called ε-zero-knowledge. Concretely, we construct the following protocols: - We construct a constant round interactive proof for NP that satisfies statistical soundness and black-box ε-zero-knowledge against quantum attacks assuming the existence of collapsing hash functions, which is a quantum counterpart of collision-resistant hash functions. Interestingly, this construction is just an adapted version of the classical protocol by Goldreich and Kahan (JoC '96) though the proof of ε-zero-knowledge property against quantum adversaries requires novel ideas. - We construct a constant round interactive argument for NP that satisfies computational soundness and black-box ε-zero-knowledge against quantum attacks only assuming the existence of post-quantum one-way functions. At the heart of our results is a new quantum rewinding technique that enables a simulator to extract a committed message of a malicious verifier while simulating verifier's internal state in an appropriate sense.

1 aChia, Nai-Hui1 aChung, Kai-Min1 aYamakawa, Takashi uhttps://arxiv.org/abs/2011.0267001291nas a2200169 4500008004100000245005900041210005900100260001400159300000900173490000900182520082200191100001701013700001801030700001901048700001701067856003701084 2020 eng d00aBuilding Bulk Geometry from the Tensor Radon Transform0 aBuilding Bulk Geometry from the Tensor Radon Transform c12/4/2020 a1-500 v20203 a

Using the tensor Radon transform and related numerical methods, we study how bulk geometries can be explicitly reconstructed from boundary entanglement entropies in the specific case of AdS3/CFT2. We find that, given the boundary entanglement entropies of a 2d CFT, this framework provides a quantitative measure that detects whether the bulk dual is geometric in the perturbative (near AdS) limit. In the case where a well-defined bulk geometry exists, we explicitly reconstruct the unique bulk metric tensor once a gauge choice is made. We then examine the emergent bulk geometries for static and dynamical scenarios in holography and in many-body systems. Apart from the physics results, our work demonstrates that numerical methods are feasible and effective in the study of bulk reconstruction in AdS/CFT.

1 aCao, ChunJun1 aQ, Xiao-Liang1 aSwingle, Brian1 aTang, Eugene uhttps://arxiv.org/abs/2007.0000401826nas a2200145 4500008004100000245009400041210006900135260001300204300001200217490000700229520136600236100002101602700002001623856003701643 2019 eng d00aBang-bang control as a design principle for classical and quantum optimization algorithms0 aBangbang control as a design principle for classical and quantum c8/1/2019 a424-4460 v193 a

Physically motivated classical heuristic optimization algorithms such as simulated annealing (SA) treat the objective function as an energy landscape, and allow walkers to escape local minima. It has been argued that quantum properties such as tunneling may give quantum algorithms advantage in finding ground states of vast, rugged cost landscapes. Indeed, the Quantum Adiabatic Algorithm (QAO) and the recent Quantum Approximate Optimization Algorithm (QAOA) have shown promising results on various problem instances that are considered classically hard. Here, we argue that the type of control strategy used by the optimization algorithm may be crucial to its success. Along with SA, QAO and QAOA, we define a new, bang-bang version of simulated annealing, BBSA, and study the performance of these algorithms on two well-studied problem instances from the literature. Both classically and quantumly, the successful control strategy is found to be bang-bang, exponentially outperforming the quasistatic analogues on the same instances. Lastly, we construct O(1)-depth QAOA protocols for a class of symmetric cost functions, and provide an accompanying physical picture.

1 aBapat, Aniruddha1 aJordan, Stephen uhttps://arxiv.org/abs/1812.0274601240nas a2200145 4500008004100000245006500041210006400106260001500170520080100185100001800986700001601004700001801020700001901038856003701057 2019 eng d00aBeyond Spontaneous Emission: Giant Atom Bounded in Continuum0 aBeyond Spontaneous Emission Giant Atom Bounded in Continuum c12/20/20193 a

The quantum coupling of individual superconducting qubits to microwave photons leads to remarkable experimental opportunities. Here we consider the phononic case where the qubit is coupled to an electromagnetic surface acoustic wave antenna that enables supersonic propagation of the qubit oscillations. This can be considered as a giant atom that is many phonon wavelengths long. We study an exactly solvable toy model that captures these effects, and find that this non-Markovian giant atom has a suppressed relaxation, as well as an effective vacuum coupling between a qubit excitation and a localized wave packet of sound, even in the absence of a cavity for the sound waves. Finally, we consider practical implementations of these ideas in current surface acoustic wave devices. 

1 aGuo, Shangjie1 aWang, Yidan1 aPurdy, Thomas1 aTaylor, J., M. uhttps://arxiv.org/abs/1912.0998001902nas a2200157 4500008004100000245011500041210006900156260001500225520137700240100001801617700001301635700001701648700001901665700002301684856003701707 2019 eng d00aButterfly effect in interacting Aubry-Andre model: thermalization, slow scrambling, and many-body localization0 aButterfly effect in interacting AubryAndre model thermalization  c02/19/20193 a

The many-body localization transition in quasiperiodic systems has been extensively studied in recent ultracold atom experiments. At intermediate quasiperiodic potential strength, a surprising Griffiths-like regime with slow dynamics appears in the absence of random disorder and mobility edges. In this work, we study the interacting Aubry-Andre model, a prototype quasiperiodic system, as a function of incommensurate potential strength using a novel dynamical measure, information scrambling, in a large system of 200 lattice sites. Between the thermal phase and the many-body localized phase, we find an intermediate dynamical phase where the butterfly velocity is zero and information spreads in space as a power-law in time. This is in contrast to the ballistic spreading in the thermal phase and logarithmic spreading in the localized phase. We further investigate the entanglement structure of the many-body eigenstates in the intermediate phase and find strong fluctuations in eigenstate entanglement entropy within a given energy window, which is inconsistent with the eigenstate thermalization hypothesis. Machine-learning on the entanglement spectrum also reaches the same conclusion. Our large-scale simulations suggest that the intermediate phase with vanishing butterfly velocity could be responsible for the slow dynamics seen in recent experiments.

1 aXu, Shenglong1 aLi, Xiao1 aHsu, Yi-Ting1 aSwingle, Brian1 aSarma, Sankar, Das uhttps://arxiv.org/abs/1902.0719901065nas a2200097 4500008004100000245006500041210006300106520074400169100001700913856003700930 2018 eng d00aA belief propagation algorithm based on domain decomposition0 abelief propagation algorithm based on domain decomposition3 a

This note provides a detailed description and derivation of the domain decomposition algorithm that appears in previous works by the author. Given a large re-estimation problem, domain decomposition provides an iterative method for assembling Boltzmann distributions associated to small subproblems into an approximation of the Bayesian posterior of the whole problem. The algorithm is amenable to using Boltzmann sampling to approximate these Boltzmann distributions. In previous work, we have shown the capability of heuristic versions of this algorithm to solve LDPC decoding and circuit fault diagnosis problems too large to fit on quantum annealing hardware used for sampling. Here, we rigorously prove soundness of the method.

1 aLackey, Brad uhttps://arxiv.org/abs/1810.1000501296nas a2200157 4500008004100000245005600041210005600097260001500153520081900168100001900987700002801006700002101034700002601055700002001081856003701101 2018 eng d00aBell monogamy relations in arbitrary qubit networks0 aBell monogamy relations in arbitrary qubit networks c2018/01/093 a

Characterizing trade-offs between simultaneous violations of multiple Bell inequalities in a large network of qubits is computationally demanding. We propose a graph-theoretic approach to efficiently produce Bell monogamy relations in arbitrary arrangements of qubits. All the relations obtained for bipartite Bell inequalities are tight and leverage only a single Bell monogamy relation. This feature is unique to bipartite Bell inequalities, as we show that there is no finite set of such elementary monogamy relations for multipartite inequalities. Nevertheless, many tight monogamy relations for multipartite inequalities can be obtained with our method as shown in explicit examples.

1 aTran, Minh, C.1 aRamanathan, Ravishankar1 aMcKague, Matthew1 aKaszlikowski, Dagomir1 aPaterek, Tomasz uhttps://arxiv.org/abs/1801.0307101804nas a2200157 4500008004100000245003600041210003600077520137400113100001701487700001801504700001901522700002401541700002501565700001901590856003701609 2018 eng d00aBlack Hole Microstate Cosmology0 aBlack Hole Microstate Cosmology3 a

In this note, we explore the possibility that certain high-energy holographic CFT states correspond to black hole microstates with a geometrical behind-the-horizon region, modelled by a portion of a second asymptotic region terminating at an end-of-the-world (ETW) brane. We study the time-dependent physics of this behind-the-horizon region, whose ETW boundary geometry takes the form of a closed FRW spacetime. We show that in many cases, this behind-the-horizon physics can be probed directly by looking at the time dependence of entanglement entropy for sufficiently large spatial CFT subsystems. We study in particular states defined via Euclidean evolution from conformal boundary states and give specific predictions for the behavior of the entanglement entropy in this case. We perform analogous calculations for the SYK model and find qualitative agreement with our expectations. A fascinating possibility is that for certain states, we might have gravity localized to the ETW brane as in the Randall-Sundrum II scenario for cosmology. In this case, the effective description of physics beyond the horizon could be a big bang/big crunch cosmology of the same dimensionality as the CFT. In this case, the d-dimensional CFT describing the black hole microstate would give a precise, microscopic description of the d-dimensional cosmological physics. 

1 aCooper, Sean1 aRozali, Moshe1 aSwingle, Brian1 aVan Raamsdonk, Mark1 aWaddell, Christopher1 aWakeham, David uhttps://arxiv.org/abs/1810.1060101515nas a2200121 4500008004100000245006500041210006500106260001500171520113200186100001901318700001901337856003701356 2018 eng d00aBlind quantum computation using the central spin Hamiltonian0 aBlind quantum computation using the central spin Hamiltonian c2018/01/113 a

Blindness is a desirable feature in delegated computation. In the classical setting, blind computations protect the data or even the program run by a server. In the quantum regime, blind computing may also enable testing computational or other quantum properties of the server system. Here we propose a scheme for universal blind quantum computation using a quantum simulator capable of emulating Heisenberg-like Hamiltonians. Our scheme is inspired by the central spin Hamiltonian in which a single spin controls dynamics of a number of bath spins. We show how, by manipulating this spin, a client that only accesses the central spin can effectively perform blind computation on the bath spins. Remarkably, two-way quantum communication mediated by the central spin is sufficient to ensure security in the scheme. Finally, we provide explicit examples of how our universal blind quantum computation enables verification of the power of the server from classical to stabilizer to full BQP computation.

1 aTran, Minh, C.1 aTaylor, J., M. uhttps://arxiv.org/abs/1801.0400601390nas a2200145 4500008004100000245007200041210006900113520091900182100002201101700002101123700001801144700002601162700001901188856003701207 2018 eng d00aBose Condensation of Photons Thermalized via Laser Cooling of Atoms0 aBose Condensation of Photons Thermalized via Laser Cooling of At3 a

A Bose-Einstein condensate (BEC) is a quantum phase of matter achieved at low temperatures. Photons, one of the most prominent species of bosons, do not typically condense due to the lack of a particle number-conservation. We recently described a photon thermalization mechanism which gives rise to a grand canonical ensemble of light with effective photon number conservation between a subsystem and a particle reservoir. This mechanism occurs during Doppler laser cooling of atoms where the atoms serve as a temperature reservoir while the cooling laser photons serve as a particle reservoir. Here we address the question of the possibility of a BEC of photons in this laser cooling photon thermalization scenario and theoretically demonstrate that a Bose condensation of photons can be realized by cooling an ensemble of two-level atoms (realizable with alkaline earth atoms) inside a Fabry-Perot cavity.

1 aWang, Chiao-Hsuan1 aGullans, Michael1 aPorto, J., V.1 aPhillips, William, D.1 aTaylor, J., M. uhttps://arxiv.org/abs/1809.0777701856nas a2200169 4500008004100000245006600041210006500107260001500172300000700187490000600194520134900200100002401549700001601573700002201589700001901611856005601630 2018 eng d00aBQP-completeness of Scattering in Scalar Quantum Field Theory0 aBQPcompleteness of Scattering in Scalar Quantum Field Theory c2018/01/08 a440 v23 a

Recent work has shown that quantum computers can compute scattering probabilities in massive quantum field theories, with a run time that is polynomial in the number of particles, their energy, and the desired precision. Here we study a closely related quantum field-theoretical problem: estimating the vacuum-to-vacuum transition amplitude, in the presence of spacetime-dependent classical sources, for a massive scalar field theory in (1+1) dimensions. We show that this problem is BQP-hard; in other words, its solution enables one to solve any problem that is solvable in polynomial time by a quantum computer. Hence, the vacuum-to-vacuum amplitude cannot be accurately estimated by any efficient classical algorithm, even if the field theory is very weakly coupled, unless BQP=BPP. Furthermore, the corresponding decision problem can be solved by a quantum computer in a time scaling polynomially with the number of bits needed to specify the classical source fields, and this problem is therefore BQP-complete. Our construction can be regarded as an idealized architecture for a universal quantum computer in a laboratory system described by massive phi^4 theory coupled to classical spacetime-dependent sources.

1 aJordan, Stephen, P.1 aKrovi, Hari1 aLee, Keith, S. M.1 aPreskill, John uhttps://quantum-journal.org/papers/q-2018-01-08-44/00671nas a2200145 4500008004100000245004500041210004400086260001400130300001000144490000700154520024100161100001800402700002100420856008400441 2018 eng d00aBroadband optomechanical non-reciprocity0 aBroadband optomechanical nonreciprocity c2018/1/26 a60-610 v123 a

Implementing non-reciprocal elements with a bandwidth comparable to optical frequencies is a challenge
in integrated photonics. Now, a phonon pump has been used to achieve optical non-reciprocity over a
large bandwidth.

1 aSeif, Alireza1 aHafezi, Mohammad uhttps://www.quics.umd.edu/publications/broadband-optomechanical-non-reciprocity01713nas a2200133 4500008004100000245007300041210006900114260001500183300001100198490000700209520120600216100001901422856013801441 2017 eng d00aBasic circuit compilation techniques for an ion-trap quantum machine0 aBasic circuit compilation techniques for an iontrap quantum mach c2016/02/20 a0230350 v193 a

We study the problem of compilation of quantum algorithms into optimized physical-level circuits executable in a quantum information processing (QIP) experiment based on trapped atomic ions. We report a complete strategy: starting with an algorithm in the form of a quantum computer program, we compile it into a high-level logical circuit that goes through multiple stages of decomposition into progressively lower-level circuits until we reach the physical execution-level specification. We skip the fault-tolerance layer, as it is not necessary in this work. The different stages are structured so as to best assist with the overall optimization while taking into account numerous optimization criteria, including minimizing the number of expensive two-qubit gates, minimizing the number of less expensive single-qubit gates, optimizing the runtime, minimizing the overall circuit error, and optimizing classical control sequences. Our approach allows a trade-off between circuit runtime and quantum error, as well as to accommodate future changes in the optimization criteria that may likely arise as a result of the anticipated improvements in the physical-level control of the experiment.

1 aMaslov, Dmitri uhttp://iopscience.iop.org/article/10.1088/1367-2630/aa5e47/meta;jsessionid=55CC235A0B106081E825099310586F07.c3.iopscience.cld.iop.org01739nam a2200109 4500008004100000245004800041210004700089260004000136520139900176100001701575856003701592 2016 eng d00aBananaworld: Quantum Mechanics for Primates0 aBananaworld Quantum Mechanics for Primates bOxford University Pressc2012/11/133 a

This is intended to be a serious paper, in spite of the title. The idea is that quantum mechanics is about probabilistic correlations, i.e., about the structure of information, since a theory of information is essentially a theory of probabilistic correlations. To make this clear, it suffices to consider measurements of two binary-valued observables, x with outcomes a = 0 or 1, performed by Alice in a region A, and y with outcomes b = 0 or 1 performed by Bob in a separated region B --or, to emphasize the banality of the phenomena, two ways of peeling a banana, resulting in one of two tastes. The imagined bananas of Bananaworld are non-standard, with operational or phenomenal probabilistic correlations for peelings and tastes that lie outside the polytope of local correlations. The 'no go' theorems tell us that we can't shoe-horn these correlations into a classical correlation polytope, which has the structure of a simplex, by supposing that something has been left out of the story, without giving up fundamental principles that define what we mean by a physical system. The nonclassical features of quantum mechanics, including the irreducible information loss on measurement, are shown to be generic features of correlations that lie outside the local correlation polytope. As far as the conceptual problems are concerned, we might as well talk about bananas.

1 aBub, Jeffrey uhttp://arxiv.org/abs/1211.3062v200790nas a2200145 4500008004100000022001400041245008400055210006900139260001500208300001200223490000700235520033900242100002400581856003900605 2016 eng d a1528-497200aBlack Holes, Quantum Mechanics, and the Limits of Polynomial-time Computability0 aBlack Holes Quantum Mechanics and the Limits of Polynomialtime C c2016/09/20 a30–330 v233 a

Which computational problems can be solved in polynomial-time and which cannot? Though seemingly technical, this question has wide-ranging implications and brings us to the heart of both theoretical computer science and modern physics.

1 aJordan, Stephen, P. uhttp://doi.acm.org/10.1145/298353901527nas a2200181 4500008004100000245006900041210006900110260001500179300001100194490000700205520098100212100002001193700002401213700002301237700002201260700002501282856003801307 2015 eng d00aBilayer fractional quantum Hall states with ultracold dysprosium0 aBilayer fractional quantum Hall states with ultracold dysprosium c2015/09/10 a0336090 v923 a We show how dipolar interactions between dysprosium atoms in an optical lattice can be used to obtain fractional quantum Hall states. In our approach, dysprosium atoms are trapped one atom per site in a deep optical lattice with negligible tunneling. Microwave and spatially dependent optical dressing fields are used to define an effective spin-1/2 or spin-1 degree of freedom in each atom. Thinking of spin-1/2 particles as hardcore bosons, dipole-dipole interactions give rise to boson hopping, topological flat bands with Chern number 1, and the \nu = 1/2 Laughlin state. Thinking of spin-1 particles as two-component hardcore bosons, dipole-dipole interactions again give rise to boson hopping, topological flat bands with Chern number 2, and the bilayer Halperin (2,2,1) state. By adjusting the optical fields, we find a phase diagram, in which the (2,2,1) state competes with superfluidity. Generalizations to solid-state magnetic dipoles are discussed. 1 aYao, Norman, Y.1 aBennett, Steven, D.1 aLaumann, Chris, R.1 aLev, Benjamin, L.1 aGorshkov, Alexey, V. uhttp://arxiv.org/abs/1505.03099v101241nas a2200157 4500008004100000245005800041210005800099260001500157300001100172490000700183520080300190100001400993700002001007700001901027856003701046 2015 eng d00aBounds on quantum communication via Newtonian gravity0 aBounds on quantum communication via Newtonian gravity c2015/01/15 a0150060 v173 aNewtonian gravity yields specific observable consequences, the most striking of which is the emergence of a $1/r^2$ force. In so far as communication can arise via such interactions between distant particles, we can ask what would be expected for a theory of gravity that only allows classical communication. Many heuristic suggestions for gravity-induced decoherence have this restriction implicitly or explicitly in their construction. Here we show that communication via a $1/r^2$ force has a minimum noise induced in the system when the communication cannot convey quantum information, in a continuous time analogue to Bell's inequalities. Our derived noise bounds provide tight constraints from current experimental results on any theory of gravity that does not allow quantum communication. 1 aKafri, D.1 aMilburn, G., J.1 aTaylor, J., M. uhttp://arxiv.org/abs/1404.3214v200466nas a2200145 4500008004100000245006400041210006400105300001100169490000800180100001700188700001700205700002500222700001400247856005900261 2014 eng d00aBeyond the spin model approximation for Ramsey spectroscopy0 aBeyond the spin model approximation for Ramsey spectroscopy a1230010 v1121 aKoller, A, P1 aBeverland, M1 aGorshkov, Alexey, V.1 aRey, A, M uhttp://link.aps.org/doi/10.1103/PhysRevLett.112.12300101367nas a2200157 4500008004100000245004300041210003700084260001500121300001200136490000900148520096000157100002301117700001801140700001401158856003701172 2014 eng d00aThe Bose-Hubbard model is QMA-complete0 aBoseHubbard model is QMAcomplete c2014/07/08 a308-3190 v85723 a The Bose-Hubbard model is a system of interacting bosons that live on the vertices of a graph. The particles can move between adjacent vertices and experience a repulsive on-site interaction. The Hamiltonian is determined by a choice of graph that specifies the geometry in which the particles move and interact. We prove that approximating the ground energy of the Bose-Hubbard model on a graph at fixed particle number is QMA-complete. In our QMA-hardness proof, we encode the history of an n-qubit computation in the subspace with at most one particle per site (i.e., hard-core bosons). This feature, along with the well-known mapping between hard-core bosons and spin systems, lets us prove a related result for a class of 2-local Hamiltonians defined by graphs that generalizes the XY model. By avoiding the use of perturbation theory in our analysis, we circumvent the need to multiply terms in the Hamiltonian by large coefficients. 1 aChilds, Andrew, M.1 aGosset, David1 aWebb, Zak uhttp://arxiv.org/abs/1311.3297v101994nas a2200121 4500008004100000245005200041210005100093260001500144300001200159520164800171100001601819856003701835 2013 eng d00aBuilding one-time memories from isolated qubits0 aBuilding onetime memories from isolated qubits c2013/04/18 a269-2863 a One-time memories (OTM's) are simple tamper-resistant cryptographic devices, which can be used to implement one-time programs, a very general form of software protection and program obfuscation. Here we investigate the possibility of building OTM's using quantum mechanical devices. It is known that OTM's cannot exist in a fully-quantum world or in a fully-classical world. Instead, we propose a new model based on "isolated qubits" -- qubits that can only be accessed using local operations and classical communication (LOCC). This model combines a quantum resource (single-qubit measurements) with a classical restriction (on communication between qubits), and can be implemented using current technologies, such as nitrogen vacancy centers in diamond. In this model, we construct OTM's that are information-theoretically secure against one-pass LOCC adversaries that use 2-outcome measurements. Our construction resembles Wiesner's old idea of quantum conjugate coding, implemented using random error-correcting codes; our proof of security uses entropy chaining to bound the supremum of a suitable empirical process. In addition, we conjecture that our random codes can be replaced by some class of efficiently-decodable codes, to get computationally-efficient OTM's that are secure against computationally-bounded LOCC adversaries. In addition, we construct data-hiding states, which allow an LOCC sender to encode an (n-O(1))-bit messsage into n qubits, such that at most half of the message can be extracted by a one-pass LOCC receiver, but the whole message can be extracted by a general quantum receiver. 1 aLiu, Yi-Kai uhttp://arxiv.org/abs/1304.5007v202607nas a2200169 4500008004100000245003500041210003200076260001500108300001200123490000600135520215500141100002002296700002002316700002302336700002002359856005802379 2012 eng d00aOn Beating the Hybrid Argument0 aBeating the Hybrid Argument c2013/11/14 a809-8430 v93 aThe hybrid argument allows one to relate the distinguishability of a distribution (from uniform) to the predictability of individual bits given a prefix. The argument incurs a loss of a factor k equal to the bit-length of the distributions: -distinguishability implies only /k-predictability. This paper studies the consequences of avoiding this loss – what we call “beating the hybrid argument” – and develops new proof techniques that circumvent the loss in certain natural settings. Specifically, we obtain the following results: 1. We give an instantiation of the Nisan-Wigderson generator (JCSS ’94) that can be broken by quantum computers, and that is o(1)-unpredictable against AC0 . This is not enough to imply indistinguishability via the hybrid argument because of the hybrid-argument loss; nevertheless, we conjecture that this generator indeed fools AC0 , and we prove this statement for a simplified version of the problem. Our conjecture implies the existence of an oracle relative to which BQP is not in the PH, a longstanding open problem. 2. We show that the “INW” generator by Impagliazzo, Nisan, and Wigderson (STOC ’94) with seed length O(log n log log n) produces a distribution that is 1/ log n-unpredictable against poly-logarithmic width (general) read-once oblivious branching programs. Thus avoiding the hybrid-argument loss would lead to a breakthrough in generators against small space. 3. We study pseudorandom generators obtained from a hard function by repeated sampling. We identify a property of functions, “resamplability,” that allows us to beat the hybrid argument, leading to new pseudorandom generators for AC0 [p] and similar classes. Although the generators have sub-linear stretch, they represent the best-known generators for these classes. Thus we establish that “beating” or bypassing the hybrid argument would have two significant consequences in complexity, and we take steps toward that goal by developing techniques that indeed beat the hybrid argument in related (but simpler) settings, leading to best-known PRGs for certain complexity classes. 1 aFefferman, Bill1 aShaltiel, Ronen1 aUmans, Christopher1 aViola, Emanuele uhttp://users.cms.caltech.edu/~umans/papers/FSUV10.pdf01436nas a2200121 4500008004100000245006400041210006300105260001500168520104800183100002301231700002301254856003701277 2009 eng d00aBlack-box Hamiltonian simulation and unitary implementation0 aBlackbox Hamiltonian simulation and unitary implementation c2009/10/223 a We present general methods for simulating black-box Hamiltonians using quantum walks. These techniques have two main applications: simulating sparse Hamiltonians and implementing black-box unitary operations. In particular, we give the best known simulation of sparse Hamiltonians with constant precision. Our method has complexity linear in both the sparseness D (the maximum number of nonzero elements in a column) and the evolution time t, whereas previous methods had complexity scaling as D^4 and were superlinear in t. We also consider the task of implementing an arbitrary unitary operation given a black-box description of its matrix elements. Whereas standard methods for performing an explicitly specified N x N unitary operation use O(N^2) elementary gates, we show that a black-box unitary can be performed with bounded error using O(N^{2/3} (log log N)^{4/3}) queries to its matrix elements. In fact, except for pathological cases, it appears that most unitaries can be performed with only O(sqrt{N}) queries, which is optimal. 1 aBerry, Dominic, W.1 aChilds, Andrew, M. uhttp://arxiv.org/abs/0910.4157v401845nas a2200145 4500008004100000245005400041210005100095260001500146300001200161520139800173100001601571700002401587700002401611856006401635 2006 eng d00aOn Bounded Distance Decoding for General Lattices0 aBounded Distance Decoding for General Lattices c2006/01/01 a450-4613 aA central problem in the algorithmic study of lattices is the closest vector problem: given a lattice L represented by some basis, and a target point y⃗ , find the lattice point closest to y⃗ . Bounded Distance Decoding is a variant of this problem in which the target is guaranteed to be close to the lattice, relative to the minimum distance λ1(L) of the lattice. Specifically, in the α-Bounded Distance Decoding problem (α-BDD), we are given a lattice L and a vector y⃗ (within distance α⋅λ1(L) from the lattice), and we are asked to find a lattice point x⃗ ∈L within distance α⋅λ1(L) from the target. In coding theory, the lattice points correspond to codewords, and the target points correspond to lattice points being perturbed by noise vectors. Since in coding theory the lattice is usually fixed, we may “pre-process” it before receiving any targets, to make the subsequent decoding faster. This leads us to consider α-BDD with pre-processing. We show how a recent technique of Aharonov and Regev [2] can be used to solve α-BDD with pre-processing in polynomial time for α=O((logn)/n−−−−−−−√). This improves upon the previously best known algorithm due to Klein [13] which solved the problem for α=O(1/n). We also establish hardness results for α-BDD and α-BDD with pre-processing, as well as generalize our results to other ℓ p norms.1 aLiu, Yi-Kai1 aLyubashevsky, Vadim1 aMicciancio, Daniele uhttp://link.springer.com/chapter/10.1007/11830924_41#page-101431nas a2200169 4500008004100000245007100041210006900112260001400181490000700195520091200202100002001114700001801134700001901152700002301171700002301194856004401217 2005 eng d00aBragg Spectroscopy of ultracold atoms loaded in an optical lattice0 aBragg Spectroscopy of ultracold atoms loaded in an optical latti c2005/8/120 v723 a We study Bragg spectroscopy of ultra-cold atoms in one-dimensional optical lattices as a method for probing the excitation spectrum in the Mott insulator phase, in particular the one particle-hole excitation band. Within the framework of perturbation theory we obtain an analytical expression for the dynamic structure factor $S(q,\omega)$ and use it to calculate the imparted energy which has shown to be a relevant observable in recent experiments. We test the accuracy of our approximations by comparing them with numerically exact solutions of the Bose-Hubbard model in restricted cases and establish the limits of validity of our linear response analysis. Finally we show that when the system is deep in the Mott insulator regime, its response to the Bragg perturbation is temperature dependent. We suggest that this dependence might be used as a tool to probe temperatures of order of the Mott gap. 1 aRey, Ana, Maria1 aBlakie, Blair1 aPupillo, Guido1 aWilliams, Carl, J.1 aClark, Charles, W. uhttp://arxiv.org/abs/cond-mat/0406552v201370nas a2200193 4500008004100000245007200041210006900113260001500182300001400197490000700211520079400218100002001012700001901032700001701051700001801068700002301086700002301109856004401132 2003 eng d00aBogoliubov approach to superfluidity of atoms in an optical lattice0 aBogoliubov approach to superfluidity of atoms in an optical latt c2003/03/14 a825 - 8410 v363 a We use the Bogoliubov theory of atoms in an optical lattice to study the approach to the Mott-insulator transition. We derive an explicit expression for the superfluid density based on the rigidity of the system under phase variations. This enables us to explore the connection between the quantum depletion of the condensate and the quasi-momentum distribution on the one hand and the superfluid fraction on the other. The approach to the insulator phase may be characterized through the filling of the band by quantum depletion, which should be directly observable via the matter wave interference patterns. We complement these findings by self-consistent Hartree-Fock-Bogoliubov-Popov calculations for one-dimensional lattices including the effects of a parabolic trapping potential. 1 aRey, Ana, Maria1 aBurnett, Keith1 aRoth, Robert1 aEdwards, Mark1 aWilliams, Carl, J.1 aClark, Charles, W. uhttp://arxiv.org/abs/cond-mat/0210550v200391nas a2200109 4500008004100000245005500041210005300096260001300149300001400162100001700176856008800193 1998 eng d00aA Bochner Vanishing Theorem for Elliptic Complexes0 aBochner Vanishing Theorem for Elliptic Complexes bSpringer a199–2261 aLackey, Brad uhttps://www.quics.umd.edu/publications/bochner-vanishing-theorem-elliptic-complexes