@article {3511, title = {Beatty Sequences for a Quadratic Irrational: Decidability and Applications}, year = {2024}, month = {2/13/2024}, abstract = {

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.

}, url = {https://arxiv.org/abs/2402.08331}, author = {Luke Schaeffer and Jeffrey Shallit and Stefan Zorcic} } @article {3365, title = {Bell sampling from quantum circuits}, year = {2023}, month = {10/6/2023}, abstract = {

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.

}, url = {https://arxiv.org/abs/2306.00083}, author = {Dominik Hangleiter and Michael Gullans} } @article {3310, title = {Bell sampling from quantum circuits}, year = {2023}, month = {6/19/2023}, abstract = {

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.

}, url = {https://arxiv.org/abs/2306.00083}, author = {Dominik Hangleiter and Michael Gullans} } @article {3360, title = {Bounds on Autonomous Quantum Error Correction}, year = {2023}, month = {8/30/2023}, abstract = {

Autonomous quantum memories are a way to passively protect quantum information using engineered dissipation that creates an \"always-on\&$\#$39;\&$\#$39; 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.

}, url = {https://arxiv.org/abs/2308.16233}, author = {Oles Shtanko and Yu-Jie Liu and Simon Lieu and Alexey V. Gorshkov and Victor V. Albert} } @article {3067, title = {Boson Sampling for Generalized Bosons}, year = {2022}, month = {5/2/2022}, abstract = {

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.

}, url = {https://arxiv.org/abs/2204.08389}, author = {En-Jui Kuo and Yijia Xu and Dominik Hangleiter and Andrey Grankin and Mohammad Hafezi} } @article {3181, title = {Bosonic coding: introduction and use cases}, year = {2022}, month = {11/10/2022}, abstract = {

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.

}, keywords = {FOS: Computer and information sciences, FOS: Physical sciences, Information Theory (cs.IT), Quantum Physics (quant-ph)}, doi = {10.48550/ARXIV.2211.05714}, url = {https://arxiv.org/abs/2211.05714}, author = {Victor V. Albert} } @article {3143, title = {Bosonic Qiskit}, year = {2022}, month = {9/22/2022}, abstract = {

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.

}, keywords = {Emerging Technologies (cs.ET), FOS: Computer and information sciences, FOS: Physical sciences, Quantum Physics (quant-ph)}, doi = {10.48550/ARXIV.2209.11153}, url = {https://arxiv.org/abs/2209.11153}, author = {Stavenger, Timothy J and Crane, Eleanor and Smith, Kevin and Kang, Christopher T and Girvin, Steven M and Wiebe, Nathan} } @article {3152, title = {Bounding the Minimum Time of a Quantum Measurement}, year = {2022}, month = {9/13/2022}, abstract = {

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.

}, keywords = {FOS: Physical sciences, Quantum Physics (quant-ph)}, doi = {10.48550/ARXIV.2209.06248}, url = {https://arxiv.org/abs/2209.06248}, author = {Shettell, Nathan and Centrone, Federico and Garc{\'\i}a-Pintos, Luis Pedro} } @article {2809, title = {Behavior of Analog Quantum Algorithms}, year = {2021}, month = {7/2/2021}, abstract = {

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.\ 

}, url = {https://arxiv.org/abs/2107.01218}, author = {Lucas T. Brady and Lucas Kocia and Przemyslaw Bienias and Aniruddha Bapat and Yaroslav Kharkov and Alexey V. Gorshkov} } @article {2581, title = {Back-action evading impulse measurement with mechanical quantum sensors}, journal = {Phys. Rev. A}, volume = {102}, year = {2020}, month = {8/28/2020}, type = {FERMILAB-PUB-19-537-T}, abstract = {

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.

}, doi = {https://doi.org/10.1103/PhysRevA.102.023525}, url = {https://arxiv.org/pdf/1910.11892.pdf}, author = {Sohitri Ghosh and Daniel Carney and Peter Shawhan and J. M. Taylor} } @article {2728, title = {A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds}, year = {2020}, month = {11/5/2020}, abstract = {

In a recent seminal work, Bitansky and Shmueli (STOC \&$\#$39;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 \&$\#$39;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\&$\#$39;s internal state in an appropriate sense.

}, url = {https://arxiv.org/abs/2011.02670}, author = {Nai-Hui Chia and Kai-Min Chung and Takashi Yamakawa} } @article {2606, title = {Building Bulk Geometry from the Tensor Radon Transform}, journal = {Journal of High Energy Physics}, volume = {2020}, year = {2020}, month = {12/4/2020}, pages = {1-50}, abstract = {

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.

}, url = {https://arxiv.org/abs/2007.00004}, author = {ChunJun Cao and Xiao-Liang Q and Brian Swingle and Eugene Tang} } @article {2321, title = {Bang-bang control as a design principle for classical and quantum optimization algorithms}, journal = {Quantum Information \& Computation }, volume = {19}, year = {2019}, month = {8/1/2019}, pages = {424-446}, abstract = {

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.

}, url = {https://arxiv.org/abs/1812.02746}, author = {Aniruddha Bapat and Stephen Jordan} } @article {2516, title = {Beyond Spontaneous Emission: Giant Atom Bounded in Continuum}, year = {2019}, month = {12/20/2019}, abstract = {

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.\ 

}, url = {https://arxiv.org/abs/1912.09980}, author = {Shangjie Guo and Yidan Wang and Thomas Purdy and J. M. Taylor} } @article {2373, title = {Butterfly effect in interacting Aubry-Andre model: thermalization, slow scrambling, and many-body localization}, year = {2019}, month = {02/19/2019}, abstract = {

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.

}, url = {https://arxiv.org/abs/1902.07199}, author = {Shenglong Xu and Xiao Li and Yi-Ting Hsu and Brian Swingle and Sankar Das Sarma} } @article {2280, title = {A belief propagation algorithm based on domain decomposition}, year = {2018}, abstract = {

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.

}, url = {https://arxiv.org/abs/1810.10005}, author = {Brad Lackey} } @article {2133, title = {Bell monogamy relations in arbitrary qubit networks}, year = {2018}, month = {2018/01/09}, abstract = {

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.

}, doi = {https://doi.org/10.1103/PhysRevA.98.052325}, url = {https://arxiv.org/abs/1801.03071}, author = {Minh C. Tran and Ravishankar Ramanathan and Matthew McKague and Dagomir Kaszlikowski and Tomasz Paterek} } @article {2298, title = {Black Hole Microstate Cosmology}, year = {2018}, abstract = {

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.\ 

}, url = {https://arxiv.org/abs/1810.10601}, author = {Sean Cooper and Moshe Rozali and Brian Swingle and Mark Van Raamsdonk and Christopher Waddell and David Wakeham} } @article {2132, title = {Blind quantum computation using the central spin Hamiltonian}, year = {2018}, month = {2018/01/11}, abstract = {

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.

}, url = {https://arxiv.org/abs/1801.04006}, author = {Minh C. Tran and J. M. Taylor} } @article {2269, title = {Bose Condensation of Photons Thermalized via Laser Cooling of Atoms}, year = {2018}, abstract = {

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.

}, url = {https://arxiv.org/abs/1809.07777}, author = {Chiao-Hsuan Wang and Michael Gullans and J. V. Porto and William D. Phillips and J. M. Taylor} } @article {1949, title = {BQP-completeness of Scattering in Scalar Quantum Field Theory}, journal = {Quantum}, volume = {2}, year = {2018}, month = {2018/01/08}, pages = {44}, abstract = {

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.

}, doi = {10.22331/q-2018-01-08-44}, url = {https://quantum-journal.org/papers/q-2018-01-08-44/}, author = {Stephen P. Jordan and Hari Krovi and Keith S. M. Lee and John Preskill} } @article {2509, title = {Broadband optomechanical non-reciprocity}, journal = {Nature Photon }, volume = {12}, year = {2018}, month = {2018/1/26}, pages = {60-61}, abstract = {

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.

}, doi = {https://doi.org/10.1038/s41566-018-0091-x}, author = {Alireza Seif and Mohammad Hafezi} } @article {1732, title = {Basic circuit compilation techniques for an ion-trap quantum machine}, journal = {New Journal of Physics}, volume = {19}, year = {2017}, month = {2016/02/20}, pages = {023035}, abstract = {

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.

}, doi = {10.1088/1367-2630/aa5e47}, url = {http://iopscience.iop.org/article/10.1088/1367-2630/aa5e47/meta;jsessionid=55CC235A0B106081E825099310586F07.c3.iopscience.cld.iop.org}, author = {Dmitri Maslov} } @book {1318, title = {Bananaworld: Quantum Mechanics for Primates}, year = {2016}, month = {2012/11/13}, publisher = {Oxford University Press}, organization = {Oxford University Press}, abstract = {

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 \&$\#$39;no go\&$\#$39; theorems tell us that we can\&$\#$39;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.

}, url = {http://arxiv.org/abs/1211.3062v2}, author = {Jeffrey Bub} } @article {1950, title = {Black Holes, Quantum Mechanics, and the Limits of Polynomial-time Computability}, journal = {XRDS}, volume = {23}, year = {2016}, month = {2016/09/20}, pages = {30{\textendash}33}, abstract = {

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.

}, issn = {1528-4972}, doi = {10.1145/2983539}, url = {http://doi.acm.org/10.1145/2983539}, author = {Stephen P. Jordan} } @article {1190, title = {Bilayer fractional quantum Hall states with ultracold dysprosium}, journal = {Physical Review A}, volume = {92}, year = {2015}, month = {2015/09/10}, pages = {033609}, abstract = { 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. }, doi = {10.1103/PhysRevA.92.033609}, url = {http://arxiv.org/abs/1505.03099v1}, author = {Norman Y. Yao and Steven D. Bennett and Chris R. Laumann and Benjamin L. Lev and Alexey V. Gorshkov} } @article {1334, title = {Bounds on quantum communication via Newtonian gravity}, journal = {New Journal of Physics}, volume = {17}, year = {2015}, month = {2015/01/15}, pages = {015006}, abstract = {Newtonian 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{\textquoteright}s inequalities. Our derived noise bounds provide tight constraints from current experimental results on any theory of gravity that does not allow quantum communication. }, doi = {10.1088/1367-2630/17/1/015006}, url = {http://arxiv.org/abs/1404.3214v2}, author = {D. Kafri and G. J. Milburn and J. M. Taylor} } @article {1839, title = {Beyond the spin model approximation for Ramsey spectroscopy}, journal = {Phys. Rev. Lett.}, volume = {112}, year = {2014}, pages = {123001}, url = {http://link.aps.org/doi/10.1103/PhysRevLett.112.123001}, author = {A P Koller and M Beverland and Alexey V. Gorshkov and A M Rey} } @article {1232, title = {The Bose-Hubbard model is QMA-complete}, journal = {Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014)}, volume = {8572}, year = {2014}, month = {2014/07/08}, pages = {308-319}, abstract = { 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. }, doi = {10.1007/978-3-662-43948-7_26}, url = {http://arxiv.org/abs/1311.3297v1}, author = {Andrew M. Childs and David Gosset and Zak Webb} } @article {1426, title = {Building one-time memories from isolated qubits}, journal = {Innovations in Theoretical Computer Science (ITCS)}, year = {2013}, month = {2013/04/18}, pages = {269-286}, abstract = { One-time memories (OTM{\textquoteright}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{\textquoteright}s using quantum mechanical devices. It is known that OTM{\textquoteright}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{\textquoteright}s that are information-theoretically secure against one-pass LOCC adversaries that use 2-outcome measurements. Our construction resembles Wiesner{\textquoteright}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{\textquoteright}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. }, doi = {10.1145/2554797.2554823}, url = {http://arxiv.org/abs/1304.5007v2}, author = {Yi-Kai Liu} } @article {1549, title = {On Beating the Hybrid Argument}, journal = {Proceedings, ITCS}, volume = {9}, year = {2012}, month = {2013/11/14}, pages = {809-843}, abstract = {The 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 {\textendash} what we call {\textquotedblleft}beating the hybrid argument{\textquotedblright} {\textendash} 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 {\textquoteright}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 {\textquotedblleft}INW{\textquotedblright} generator by Impagliazzo, Nisan, and Wigderson (STOC {\textquoteright}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, {\textquotedblleft}resamplability,{\textquotedblright} 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 {\textquotedblleft}beating{\textquotedblright} 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. }, url = {http://users.cms.caltech.edu/~umans/papers/FSUV10.pdf}, author = {Bill Fefferman and Ronen Shaltiel and Christopher Umans and Emanuele Viola} } @article {1220, title = {Black-box Hamiltonian simulation and unitary implementation}, year = {2009}, month = {2009/10/22}, abstract = { 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. }, url = {http://arxiv.org/abs/0910.4157v4}, author = {Dominic W. Berry and Andrew M. Childs} } @article {1589, title = {On Bounded Distance Decoding for General Lattices}, journal = {Proc. RANDOM}, year = {2006}, month = {2006/01/01}, pages = {450-461}, abstract = {A 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 {\textquotedblleft}pre-process{\textquotedblright} 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 l p norms.}, url = {http://link.springer.com/chapter/10.1007/11830924_41$\#$page-1}, author = {Yi-Kai Liu and Vadim Lyubashevsky and Daniele Micciancio} } @article {1415, title = {Bragg Spectroscopy of ultracold atoms loaded in an optical lattice}, journal = {Physical Review A}, volume = {72}, year = {2005}, month = {2005/8/12}, abstract = { 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. }, doi = {10.1103/PhysRevA.72.023407}, url = {http://arxiv.org/abs/cond-mat/0406552v2}, author = {Ana Maria Rey and P. Blair Blakie and Guido Pupillo and Carl J. Williams and Charles W. Clark} } @article {1414, title = {Bogoliubov approach to superfluidity of atoms in an optical lattice}, journal = {Journal of Physics B: Atomic, Molecular and Optical Physics}, volume = {36}, year = {2003}, month = {2003/03/14}, pages = {825 - 841}, abstract = { 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. }, doi = {10.1088/0953-4075/36/5/304}, url = {http://arxiv.org/abs/cond-mat/0210550v2}, author = {Ana Maria Rey and Keith Burnett and Robert Roth and Mark Edwards and Carl J. Williams and Charles W. Clark} } @inbook {1778, title = {A Bochner Vanishing Theorem for Elliptic Complexes}, booktitle = {The Theory of Finslerian Laplacians and Applications}, year = {1998}, pages = {199{\textendash}226}, publisher = {Springer}, organization = {Springer}, author = {Lackey, Brad} }