- Jan 15 2018 quant-ph arXiv:1801.04255v1Surface codes are the leading family of quantum error-correcting codes. Here, we explore the properties of the 3D surface code. We develop a new picture for visualising 3D surface codes which can be used to analyse the properties of stacks of three 3D surface codes. We then use our new picture to prove that the $CCZ$ gate is transversal in 3D surface codes. We also generalise the techniques of lattice surgery to 3D surface codes. Finally, we introduce a hybrid 2D/3D surface code architecture which supports universal quantum computation without magic state distillation.
- We show how to approximately represent a quantum state using the square root of the usual amount of classical memory. The classical representation of an n-qubit state $\psi$ consists of its inner products with $O(\sqrt{2^n})$ stabilizer states. A quantum state initially specified by its $2^n$ entries in the computational basis can be compressed to this form in time $O(2^n \mathrm{poly}(n))$, and, subsequently, the compressed description can be used to additively approximate the expectation value of an arbitrary observable. Our compression scheme directly gives a new protocol for the vector in subspace problem with randomized one-way communication complexity that matches (up to polylogarithmic factors) the best known upper bound, due to Raz. We obtain an exponential improvement over Raz's protocol in terms of computational efficiency.
- Jan 16 2018 quant-ph arXiv:1801.04795v1Permutational Quantum Computing (Jordan, 2009) is a natural quantum computational model that was conjectured to capture non-classical aspects of quantum computation. Contrary to the previous conjecture, we find a classical algorithm that efficiently approximates output distributions of the model up to polynomially small additive precision. We extend this algorithm to show that a large class of important quantum circuits - the Quantum Schur Sampling circuits - can be also efficiently simulated classically. The algorithm can be used to efficiently estimate non-trivial elements of irreducible representation matrices of the symmetric group on $n$ elements and might be also used to approximate transition amplitudes of the Ponzano-Regge model.
- Jan 17 2018 quant-ph cond-mat.str-el arXiv:1801.05390v1We describe an approach to fix the gauge degrees of freedom in tensor networks, including those with closed loops, which allows a canonical form for arbitrary tensor networks to be realized. Additionally, a measure for the internal correlations present in a tensor network is proposed, which quantifies the extent of resonances around closed loops in the network. Finally we describe an algorithm for the optimal truncation of an internal index from a tensor network, based upon proper removal of the redundant internal correlations. These results, which offer a unified theoretical framework for the manipulation of tensor networks with closed loops, can be applied to improve existing tensor network methods for the study of many-body systems and may also constitute key algorithmic components of sophisticated new tensor methods.
- Jan 15 2018 quant-ph arXiv:1801.04042v1Standard randomized benchmarking protocols entail sampling from a unitary 2 design, which is not always practical. In this article we examine randomized benchmarking protocols based on subgroups of the Clifford group that are not unitary 2 designs. We introduce a general method for analyzing such protocols and subsequently apply it to two subgroups, the group generated by controlled-NOT, Hadamard, and Pauli gates and that generated by only controlled-NOT and Pauli gates. In both cases the error probability can be estimated to within a factor of two or less where the factor can be arranged to be conservative and to decay exponentially in the number of qubits. For randomized benchmarking of logical qubits even better accuracy will typically be obtained. Thus, we show that sampling a distribution which is close to a unitary 2 design, although sufficient, is not necessary for randomized benchmarking to high accuracy.
- Jan 18 2018 quant-ph arXiv:1801.05450v1We develop a general framework characterizing the structure and properties of quantum resource theories for continuous-variable Gaussian states and Gaussian operations, establishing methods for their description and quantification. We show in particular that, under a few intuitive and physically-motivated assumptions on the set of free states, no Gaussian quantum resource can be distilled with Gaussian free operations, even when an unlimited supply of the resource state is available. This places fundamental constraints on state transformations in all such Gaussian resource theories. Our methods rely on the definition of a general Gaussian resource quantifier whose value does not change when multiple copies are considered. We discuss in particular the applications to quantum entanglement, where we extend previously known results by showing that Gaussian entanglement cannot be distilled even with Gaussian operations preserving the positivity of the partial transpose, as well as to other Gaussian resources such as steering and optical nonclassicality. A unified semidefinite programming representation of all these resources is provided.
- Jan 17 2018 quant-ph arXiv:1801.05237v1The so-called information-thermodynamics link has been created in a series of works starting from Maxwell demon and established by the idea of transforming information into work in the though experiment of Szilard which then evolved into the vast field of research. The aim of this note is firstly to present two new models of the Szilard engine containing arbitrary number of molecules which show irrelevance of acquiring information for work extraction. Secondly, the difference between the definition of entropy for ergodic systems and systems with ergodicity breaking constraints is emphasized. The role of nonergodic systems as information carriers and the thermodynamic cost of stability and accuracy of information encoding and processing is briefly discussed.
- The approximate degree of a Boolean function $f(x_{1},x_{2},\ldots,x_{n})$ is the minimum degree of a real polynomial that approximates $f$ pointwise within $1/3$. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree arise in an existential manner from bounds on quantum query complexity. We develop a first-principles, classical approach to the polynomial approximation of Boolean functions. We use it to give the first constructive upper bounds on the approximate degree of several fundamental problems: - $O\bigl(n^{\frac{3}{4}-\frac{1}{4(2^{k}-1)}}\bigr)$ for the $k$-element distinctness problem; - $O(n^{1-\frac{1}{k+1}})$ for the $k$-subset sum problem; - $O(n^{1-\frac{1}{k+1}})$ for any $k$-DNF or $k$-CNF formula; - $O(n^{3/4})$ for the surjectivity problem. In all cases, we obtain explicit, closed-form approximating polynomials that are unrelated to the quantum arguments from previous work. Our first three results match the bounds from quantum query complexity. Our fourth result improves polynomially on the $\Theta(n)$ quantum query complexity of the problem and refutes the conjecture by several experts that surjectivity has approximate degree $\Omega(n)$. In particular, we exhibit the first natural problem with a polynomial gap between approximate degree and quantum query complexity.
- We analyze certain class of linear maps on matrix algebras that become entanglement breaking after composing a finite or infinite number of times with themselves. This means that the Choi matrix of the iterated linear map becomes separable in the tensor product space. If a linear map is entanglement breaking after finite iterations, we say the map has a finite index of separability. In particular we show that every unital PPT-channel becomes entanglement breaking after a finite number of iterations. It turns out that the class of unital channels that have finite index of separability is a dense subset of the unital channels. We construct concrete examples of maps which are not PPT but have finite index of separability. We prove that there is a large class of unital channels that are asymptotically entanglement breaking. This analysis is motivated by the PPT-squared conjecture made by M. Christandl that says every PPT channel, when composed with itself, becomes entanglement breaking.
- Jan 15 2018 quant-ph arXiv:1801.04043v1A central theme in quantum information science is to coherently control an increasing number of quantum particles as well as their internal and external degrees of freedom (DoFs), meanwhile maintaining a high level of coherence. The ability to create and verify multiparticle entanglement with individual control and measurement of each qubit serves as an important benchmark for quantum technologies. To this end, genuine multipartite entanglement have been reported up to 14 trapped ions, 10 photons, and 10 superconducting qubits. Here, we experimentally demonstrate an 18-qubit Greenberger-Horne-Zeilinger (GHZ) entanglement by simultaneous exploiting three different DoFs of six photons, including their paths, polarization, and orbital angular momentum (OAM). We develop high-stability interferometers for reversible quantum logic operations between the photon's different DoFs with precision and efficiencies close to unity, enabling simultaneous readout of 262,144 outcome combinations of the 18-qubit state. A state fidelity of 0.708(16) is measured, confirming the genuine entanglement of all the 18 qubits.
- Jan 15 2018 quant-ph arXiv:1801.04006v1Blindness 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.
- Jan 16 2018 quant-ph arXiv:1801.04807v2Two primary facets of quantum technological advancement that hold great promise are quantum communication and quantum computation. For quantum communication, the canonical resource is entanglement. For quantum gate implementation, the resource is 'magic' in an auxiliary system. It has already been shown that quantum coherence is the fundamental resource for the creation of entanglement. We argue on the similar spirit that quantum coherence is the fundamental resource when it comes to the creation of magic. This unifies the two strands of modern development in quantum technology under the common underpinning of existence of quantum superposition, quantified by the coherence in quantum theory. We also attempt to obtain magic monotones inspired from coherence monotones and vice versa. We further study the interplay between quantum coherence and magic in a qutrit system and that between quantum entanglement and magic in a qutrit-qubit setting.
- Jan 17 2018 quant-ph arXiv:1801.05185v1The accessible information and the informational power quantify the maximum amount of information that can be extracted from a quantum ensemble and by a quantum measurement, respectively. Here, we investigate the tradeoff between the accessible information (informational power, respectively) and the purity of the states of the ensemble (the elements of the measurement, respectively). Under any given lower bound on the purity, i) we compute the minimum informational power and show that it is attained by the depolarized uniformly-distributed measurement; ii) we give a lower bound on the accessible information. Under any given upper bound on the purity, i) we compute the maximum accessible information and show that it is attained by an ensemble of pairwise commuting states with at most two distinct non-null eigenvalues; ii) we give a lower bound on the maximum informational power. The present results provide, as a corollary, novel sufficient conditions for the tightness of the Jozsa-Robb-Wootters lower bound to the accessible information.
- Jan 17 2018 quant-ph arXiv:1801.05123v1The use of imaginary numbers in modelling quantum mechanical systems encompasses the wave-like nature of quantum states. Here we introduce a resource theoretic framework for imaginarity, where the free states are taken to be those with density matrices that are real with respect to a fixed basis. This theory is closely related to the resource theory of coherence, as it is basis dependent, and the imaginary numbers appear in the off-diagonal elements of the density matrix. Unlike coherence however, the set of physically realizable free operations is identical to both completely resource non-generating operations, and stochastically resource non-generating operations. Moreover, the resource theory of imaginarity does not have a self-adjoint resource destroying map. After introducing and characterizing the free operations, we provide several measures of imaginarity, and give necessary and sufficient conditions for pure state transformations via physically consistent free operations in the single shot regime.
- Jan 17 2018 quant-ph arXiv:1801.05283v1A quantum computer has the potential to effciently solve problems that are intractable for classical computers. Constructing a large-scale quantum processor, however, is challenging due to errors and noise inherent in real-world quantum systems. One approach to this challenge is to utilize modularity--a pervasive strategy found throughout nature and engineering--to build complex systems robustly. Such an approach manages complexity and uncertainty by assembling small, specialized components into a larger architecture. These considerations motivate the development of a quantum modular architecture, where separate quantum systems are combined via communication channels into a quantum network. In this architecture, an essential tool for universal quantum computation is the teleportation of an entangling quantum gate, a technique originally proposed in 1999 which, until now, has not been realized deterministically. Here, we experimentally demonstrate a teleported controlled-NOT (CNOT) operation made deterministic by utilizing real-time adaptive control. Additionally, we take a crucial step towards implementing robust, error-correctable modules by enacting the gate between logical qubits, encoding quantum information redundantly in the states of superconducting cavities. Such teleported operations have significant implications for fault-tolerant quantum computation, and when realized within a network can have broad applications in quantum communication, metrology, and simulations. Our results illustrate a compelling approach for implementing multi-qubit operations on logical qubits within an error-protected quantum modular architecture.
- Let T_1 be an k_1-tensor and let T_2 be a k_2-tensor and consider the tensor product of T_1 ⊗T_2, which is a (k_1 + k_2)-tensor. It has recently been shown ([Christandl, Jensen, Zuiddam]) that the tensor rank can be strictly submultiplicative under the tensor product. The necessary upper bounds were obtained with help of the border rank. It was left open whether border rank itself can be strictly submultiplicative. In the current work, we answer this question in the affirmative. In order to do so, we construct lines in projective space along which the border rank drops multiple times and use this result in conjunction with a previous construction for a tensor rank drop. Our results also imply strict submultiplicativity for cactus rank and border cactus rank.
- We consider the uncertainty between two pairs of local projective measurements performed on a multipartite system. We show that the optimal bound in any linear uncertainty relation, formulated in terms of the Shannon entropy, is additive. This directly implies, against naive intuition, that the minimal entropic uncertainty can always be realized by fully separable states. Hence, in contradiction to proposals by other authors, no entanglement witness can be constructed solely by comparing the attainable uncertainties of entangled and separable states. However, our result gives rise to a huge simplification for computing global uncertainty bounds as they now can be deduced from local ones. Furthermore, we provide the natural generalization of the Massen and Uffink inequality for linear uncertainty relations with arbitrary positive coefficients.
- We extend the concept of strange correlators, defined for symmetry-protected phases in [You et al., Phys. Rev. Lett. 112, 247202 (2014)], to topological phases of matter by taking the inner product between string-net ground states and product states. The resulting two-dimensional partition functions are shown to be either critical or symmetry broken, as the corresponding transfer matrices inherit all matrix product operator symmetries of the string-net states. For the case of critical systems, those non-local matrix product operator symmetries are the lattice remnants of topological conformal defects in the field theory description. Following [Aasen et al., J. Phys. A 49, 354001 (2016)], we argue that the different conformal boundary conditions can be obtained by applying the strange correlator concept to the different topological sectors of the string-net obtained from Ocneanu's tube algebra. This is demonstrated by calculating the conformal field theory spectra on the lattice in the different topological sectors for the Fibonacci/hard-hexagon and Ising string-net. Additionally, we provide a complementary perspective on symmetry-preserving real-space renormalization by showing how known tensor network renormalization methods can be understood as the approximate truncation of an exactly coarse-grained strange correlator.
- Jan 17 2018 quant-ph arXiv:1801.05057v1We present a simple protocol for certifying graph states in quantum networks using stabiliser measurements. The certification statements can easily be applied to different protocols using graph states. We see for example how it can be used to for measurement based verified quantum compu- tation, certified sampling of random unitaries and quantum metrology and sharing quantum secrets over untrusted channels.
- Jan 19 2018 quant-ph arXiv:1801.06121v1Randomized benchmarking provides a tool for obtaining precise quantitative estimates of the average error rate of a physical quantum channel. Here we define real randomized benchmarking, which enables a separate determination of the average error rate in the real and complex parts of the channel. This provides more fine-grained information about average error rates with approximately the same cost as the standard protocol. The protocol requires only averaging over the real Clifford group, a subgroup of the full Clifford group, and makes use of the fact that it forms an orthogonal 2-design. Our results are therefore especially useful when considering quantum computations on rebits (or real encodings of complex computations), in which case the real Clifford group now plays the role of the complex Clifford group when studying stabilizer circuits.
- The existing multi-prover interactive proof framework suffers from incompleteness in terms of soundness and zero-knowledge that is not completely addressed in the literature. The problem is that the existing definitions of what is local, entangled and no-signalling are not rich enough to capture the full generality of multi-prover interaction. In general, existing proofs do not take into account possible changes in locality either during a protocol's execution or when protocols are composed together. This is especially problematic for zero-knowledge, as composing commitments is the only known way of achieving zero-knowledge outside of some NP-intermediate languages. In this work, we introduce the locality hierarchy for multiparty (multi-round) interaction, and for the first time a complete definition of multi-round multiparty no-signalling distributions and strategies. Within this framework, we define the locality of a protocol which involves the provers, verifiers, simulators and distinguishers. We show that an existing protocol for NEXP [BFL90] and a zero-knowledge variant we introduce are sound in a local sense, but are zero-knowledge in a sense that is even stronger than usually understood. All prior claims of zero-knowledge proofs in the multi-prover model were actually incorrect. Finally, we present similar constructions for entangled and no-signalling prover sets for NEXP and EXP based on [IV12] and [KRR14] using new multi-prover commitment schemes.
- Alice is transmitting a private message to Bob across a bosonic wiretap channel with the help of a public feedback channel to which all parties, including the fully-quantum equipped Eve, have completely noiseless access. We find that by altering the model such that Eve's copy of the initial round of feedback is corrupted by an iota of noise, one step towards physical relevance, the capacity can be increased dramatically. It is known that the private capacity with respect to the original model for a pure-loss bosonic channel is at most $- \log(1-\eta)$ bits per mode, where $\eta$ is the transmissivity, in the limit of infinite input photon number. This is a very pessimistic result as there is a finite rate limit even with an arbitrarily large number of input photons. We refer to this as a loss limited rate. However, in our altered model we find that we can achieve a rate of $(1/2) \log(1 + 4 \eta N_S)$ bits per mode, where $N_S$ is the input photon number. This rate diverges with $N_S$, in sharp contrast to the result for the original model. This suggests that physical considerations behind the eavesdropping model should be taken more seriously, as they can create strong dependencies of the achievable rates on the model. For by a seemingly inconsequential weakening of Eve, we obtain a loss-unlimited rate. Our protocol also works verbatim for arbitrary i.i.d. noise (not even necessarily Gaussian) injected by Eve in every round, and even if Eve is given access to copies of the initial transmission and noise. The error probability of the protocol decays super-exponentially with the blocklength.
- Jan 16 2018 quant-ph arXiv:1801.04418v1We perform decoy-state quantum key distribution between a low-Earth-orbit satellite and multiple ground stations located in Xinglong, Nanshan, and Graz, which establish satellite-to-ground secure keys with ~kHz rate per passage of the satellite Micius over a ground station. The satellite thus establishes a secure key between itself and, say, Xinglong, and another key between itself and, say, Graz. Then, upon request from the ground command, Micius acts as a trusted relay. It performs bitwise exclusive OR operations between the two keys and relays the result to one of the ground stations. That way, a secret key is created between China and Europe at locations separated by 7600 km on Earth. These keys are then used for intercontinental quantum-secured communication. This was on the one hand the transmission of images in a one-time pad configuration from China to Austria as well as from Austria to China. Also, a videoconference was performed between the Austrian Academy of Sciences and the Chinese Academy of Sciences, which also included a 280 km optical ground connection between Xinglong and Beijing. Our work points towards an efficient solution for an ultralong-distance global quantum network, laying the groundwork for a future quantum internet.
- Jan 16 2018 quant-ph arXiv:1801.04377v1Quantum error correction is an essential technique for constructing a scalable quantum computer. In order to implement quantum error correction with near-term quantum devices, a fast and near-optimal decoding method is demanded. A decoder based on machine learning is considered as one of the most viable solutions for this purpose, since its prediction is fast once training has been done, and it is applicable to any quantum error correcting codes and any noise models. So far, various formulations of the decoding problem as the task of machine learning has been proposed. Here, we discuss general constructions of machine-learning-based decoders. We found several conditions to achieve near-optimal performance, and proposed a criterion which should be optimized when a size of training data set is limited. We also discuss preferable constructions of neural networks, and proposed a decoder using spatial structures of topological codes using a convolutional neural network. We numerically show that our method can improve the performance of machine-learning-based decoders in various topological codes and noise models.
- We prove that for any $\lambda > 1$, fixed in advance, the permanent of an $n \times n$ complex matrix, where the absolute value of each diagonal entry is at least $\lambda$ times bigger than the sum of the absolute values of all other entries in the same row, can be approximated within any relative error $0 < \epsilon < 1$ in quasi-polynomial $n^{O(\ln n - \ln \epsilon)}$ time. We extend this result to multidimensional permanents of tensors and discuss its application to weighted counting of perfect matchings in hypergraphs.
- We introduce a driven-dissipative two-mode bosonic system whose reservoir causes simultaneous loss of two photons in each mode and whose steady states are superpositions of pair-coherent/Barut-Girardello coherent states. We show how quantum information encoded in a steady-state subspace of this system is exponentially immune to phase drifts (cavity dephasing) in both modes. Additionally, it is possible to protect information from arbitrary photon loss in either (but not simultaneously both) of the modes by continuously monitoring the difference between the expected photon numbers of the logical states. Despite employing more resources, the two-mode scheme enjoys two advantages over its one-mode counterpart with regards to implementation using current circuit QED technology. First, monitoring the photon number difference can be done without turning off the currently implementable dissipative stabilizing process. Second, a lower average photon number per mode is required to enjoy a level of protection at least as good as that of the cat-codes. We discuss circuit QED proposals to stabilize the code states, perform gates, and protect against photon loss via either active syndrome measurement or an autonomous procedure. We introduce quasiprobability distributions allowing us to represent two-mode states of fixed photon number difference in a two-dimensional complex plane, instead of the full four-dimensional two-mode phase space. The two-mode codes are generalized to multiple modes in an extension of the stabilizer formalism to non-diagonalizable stabilizers. The $M$-mode codes can protect against either arbitrary photon losses in up to $M-1$ modes or arbitrary losses or gains in any one mode.
- We present a theory of quantum gravity that combines a geometrical formulation of quantum field theory in space-time with classical Einstein's general relativity. This approach is based on the geometrization of quantum mechanics proposed in refs.[1,2] and combines quantum and gravitational effects into a global curvature of the Finsler's space associated to the 4N-dimensional configuration space of a N-particle system. In order to make this theory compatible with general relativity, the quantum effects are described in the framework of quantum field theory, where a covariant definition of 'simultaneity' for many-body systems is introduced through the definition of a suited foliation of space-time. As for Einstein's classical gravitation theory, the particles dynamics is finally described by means of a geodesic equation in a curved space-time manifold.
- We introduce a general framework for de Finetti reduction results, applicable to various notions of partially exchangeable probability distributions. Explicit statements are derived for the cases of exchangeability, Markov exchangeability, and some generalizations of these. Our techniques are combinatorial and rely on the "BEST" theorem, enumerating the Eulerian cycles of a multigraph.
- Jan 17 2018 cs.CC arXiv:1801.05202v1In this paper we propose models of combinatorial algorithms for the Boolean Matrix Multiplication (BMM), and prove lower bounds on computing BMM in these models. First, we give a relatively relaxed combinatorial model which is an extension of the model by Angluin (1976), and we prove that the time required by any algorithm for the BMM is at least $\Omega(n^3 / 2^{O( \sqrt{ \log n })})$. Subsequently, we propose a more general model capable of simulating the "Four Russians Algorithm". We prove a lower bound of $\Omega(n^{7/3} / 2^{O(\sqrt{ \log n })})$ for the BMM under this model. We use a special class of graphs, called $(r,t)$-graphs, originally discovered by Rusza and Szemeredi (1978), along with randomization, to construct matrices that are hard instances for our combinatorial models.
- We explore the possibility of efficient classical simulation of linear optics experiments under the effect of particle losses. Specifically, we investigate the canonical boson sampling scenario in which an $n$-particle Fock input state propagates through a linear-optical network and is subsequently measured by particle-number detectors in the $m$ output modes. We examine two models of losses. In the first model a fixed number of particles is lost. We prove that in this scenario the output statistics can be well approximated by an efficient classical simulation, provided that the number of photons that is left grows slower than $\sqrt{n}$. In the second loss model, every time a photon passes through a beamsplitter in the network, it has some probability of being lost. For this model the relevant parameter is $s$, the smallest number of beamsplitters that any photon traverses as it propagates through the network. We prove that it is possible to approximately simulate the output statistics already if $s$ grows logarithmically with $m$, regardless of the geometry of the network. The latter result is obtained by proving that it is always possible to commute $s$ layers of uniform losses to the input of the network regardless of its geometry, which could be a result of independent interest. We believe that our findings put strong limitations on future experimental realizations of quantum computational supremacy proposals based on boson sampling.
- An efficient variational approach is developed to solve in- and out-of-equilibrium problems of generic quantum spin-impurity systems. Employing the discrete symmetry hidden in spin-impurity models, we present a new canonical transformation that completely decouples the impurity and bath degrees of freedom. Combining it with Gaussian states, we present a family of many-body states to efficiently encode nontrivial impurity-bath correlations. We demonstrate its successful application to the anisotropic and two-lead Kondo models by studying their spatiotemporal dynamics, universal nonperturbative scaling and transport phenomena, and compare to other analytical and numerical approaches. In particular, we apply our method to study new types of nonequilibrium phenomena that have not been studied by other methods, such as long-time crossover in the ferromagnetic easy-plane Kondo model. Our results can be tested in experiments with mesoscopic electron systems and ultracold atoms in optical lattices.
- The weight decision problem, which requires to determine the Hamming weight of a given binary string, is a natural and important problem, with applications in cryptanalysis, coding theory, fault-tolerant circuit design and so on. In particular, both Deutsch-Jozsa problem and Grover search problem can be interpreted as special cases of weight decision problems. In this work, we investigate the exact quantum query complexity of weight decision problems, where the quantum algorithm must always output the correct answer. More specifically we consider a partial Boolean function which distinguishes whether the Hamming weight of the length-$n$ input is $k$ or it is $l$. Our contribution includes both upper bounds and lower bounds for the precise number of queries. Furthermore, for most choices of $(\frac{k}{n},\frac{l}{n})$ and sufficiently large $n$, the gap between our upper and lower bounds is no more than one. To get the results, we first build the connection between Chebyshev polynomials and our problem, then determine all the boundary cases of $(\frac{k}{n},\frac{l}{n})$ with matching upper and lower bounds, and finally we generalize to other cases via a new \emphquantum padding technique. This quantum padding technique can be of independent interest in designing other quantum algorithms.
- Jan 17 2018 hep-th arXiv:1801.05289v1In this paper we propose a space-time random tensor network approach for understanding holographic duality. Using tensor networks with random link projections, we define boundary theories with interesting holographic properties, such as the Renyi entropies satisfying the covariant Hubeny-Rangamani-Takayanagi formula, and operator correspondence with local reconstruction properties. We also investigate the unitarity of boundary theory in spacetime geometries with Lorenzian signature. Compared with the spatial random tensor networks, the space-time generalization does not require a particular time slicing, and provides a more covariant family of microscopic models that may help us to understand holographic duality.
- We consider a model of communication via a fully quantum jammer channel with quantum jammer, quantum sender and quantum receiver, which we dub quantum arbitrarily varying channel (QAVC). Restricting to finite dimensional user and jammer systems, we show, using permutation symmetry and a de Finetti reduction, how the random coding capacity (classical and quantum) of the QAVC is reduced to the capacity of a naturally associated compound channel, which is obtained by restricting the jammer to i.i.d. input states. Furthermore, we demonstrate that the shared randomness required is at most logarithmic in the block length, using a random matrix tail bound. This implies a dichotomy theorem: either the classical capacity of the QAVC is zero, and then also the quantum capacity is zero, or each capacity equals its random coding variant.
- Jan 16 2018 math.QA arXiv:1801.04296v1Acyclic anyon models are non-abelian anyon models for which thermal anyon errors can be corrected. In this note, we characterize acyclic anyon models and raise the question if the restriction to acyclic anyon models is a deficiency of the current protocol or could it be intrinsically related to the computational power of non-abelian anyons. We also obtain general results on acyclic anyon models and find new acyclic anyon models such as $SO(8)_2$ and untwisted Dijkgraaf-Witten theories of nilpotent finite groups.
- Jan 15 2018 quant-ph arXiv:1801.03947v2We investigate theoretically the efficiency of deep-space optical communication in the presence of background noise. With decreasing average signal power spectral density, a scaling gap opens up between optimized simple-decoded pulse position modulation and generalized on-off keying with direct detection. The scaling of the latter follows the quantum mechanical capacity of an optical channel with additive Gaussian noise. Efficient communication is found to require a highly imbalanced distribution of instantaneous signal power. This condition can be alleviated through the use of structured receivers which exploit optical interference over multiple time bins to concentrate the signal power before the detection stage.
- Jan 18 2018 quant-ph arXiv:1801.05798v1This paper reconstructs quantum theory from operational principles starting from something we dub an effect theory, a generalisation of operational probabilistic theories that does not have any monoidal structure and does not a priori refer to the real numbers, allowing a study of more exotic theories. Our first postulates require the existence of initial filters and final compressions for effects, a variation of the ideal compression axiom of Chiribella et al. (2011). Restricting to the standard operational setting (real probabilities, finite-dimensional) we show that this leads to the existence of spectral decompositions of effects in terms of sharp effects. In the presence of two additional postulates that are relatively standard (composition of pure maps being pure again, and the existence of a transitive symmetry group) we show that the systems must be Euclidean Jordan algebras. Finally we add an "observability of energy" condition (Barnum et al. 2014) to complete the reconstruction of quantum theory.
- Jan 16 2018 quant-ph cond-mat.mes-hall arXiv:1801.04858v2Fast, high-fidelity single and two-qubit gates are essential to building a viable quantum information processor, but achieving both in the same system has proved challenging for spin qubits. We propose and analyze an approach to perform a long-distance two-qubit controlled phase (CPHASE) gate between two singlet-triplet qubits using an electromagnetic resonator to mediate their interaction. The qubits couple longitudinally to the resonator, and by driving the qubits near the resonator's frequency they can be made to acquire a state-dependent geometric phase that leads to a CPHASE gate independent of the initial state of the resonator. Using high impedance resonators enables gate times of order 10 ns while maintaining long coherence times. Simulations show average gate fidelities of over 96% using currently achievable experimental parameters and over 99% using state-of-the-art resonator technology. After optimizing the gate fidelity in terms of parameters tuneable in-situ, we find it takes a simple power-law form in terms of the resonator's impedance and quality and the qubits' noise bath.
- Jan 16 2018 quant-ph arXiv:1801.04805v1The quantum walk (QW) was introduced as a quantum counterpart of the classical random walk. A number of non-classical properties of the QW have been shown, e.g., ballistic spreading, anti-bellshaped limit density, localization. Since around 2000, extensive research has been conducted in both theoretical aspects as well as the practical application of QWs. However, the application of a QW to the time-series analysis is not known. On the other hand, it is well known that the ARMA or GARCH models have been widely used in economics and finance. These models are studied under some suitable stationarity conditions. In this paper, we propose a new time-series model based on the QW, which does not assume such a stationarity. Therefore, our method would be applicable to the non-stationary time series.
- Jan 16 2018 quant-ph arXiv:1801.04364v1We expand the time reversal symmetry arguments of quantum mechanics, originally proposed by Wigner in the context of unitary dynamics, to contain situations including generalized measurements for monitored quantum systems. We propose a scheme to derive the time reversed measurement operators by considering the Schrödinger picture dynamics of a qubit coupled to a measuring device, and show that the time reversed measurement operators form a Positive Operator Valued Measure (POVM) set. We propose a general rule to reverse any rank two qubit measurement, and show that the time reversed dynamics obeys the retrodicted equations of the forward dynamics starting from the time reversed final state. We present three particular examples to illustrate time reversal of measurements: (1) the Gaussian spin measurement, (2) a dichotomous POVM for spin, and (3) the measurement of qubit fluorescence. We demonstrate the time reversal invariance of dynamical equations using the example of qubit fluorescence. We also generalize the discussion of a statistical arrow of time for continuous quantum measurements introduced by Dressel et al. [Phys. Rev. Lett. 119, 220507 (2017)]: we show that the backward probabilities can be computed from a process similar to retrodiction from the time reversed final state, and extend the definition of an arrow of time to ensembles prepared with pre- and post-selections, where we obtain a non-vanishing arrow of time in general. We discuss sufficient conditions for when time's arrow vanishes and show our method also captures the contributions to time's arrow due to natural physical processes like relaxation of an atom to its ground state. As a special case, we recover the time reversibility of the weak value as its complex conjugate using our method, and discuss how our conclusions differ from the time-symmetry argument of Aharonov-Bergmann-Lebowitz (ABL) rule.
- We construct examples of translationally invariant solvable models of strongly-correlated metals, composed of lattices of Sachdev-Ye-Kitaev dots with identical local interactions. These models display crossovers as a function of temperature into regimes with local quantum criticality and marginal-Fermi liquid behavior. In the marginal Fermi liquid regime, the dc resistivity increases linearly with temperature over a broad range of temperatures. By generalizing the form of interactions, we also construct examples of non-Fermi liquids with critical Fermi-surfaces. The self energy has a singular frequency dependence, but lacks momentum dependence, reminiscent of a dynamical mean field theory-like behavior but in dimensions $d<\infty$. In the low temperature and strong-coupling limit, a heavy Fermi liquid is formed. The critical Fermi-surface in the non-Fermi liquid regime gives rise to quantum oscillations in the magnetization as a function of an external magnetic field in the absence of quasiparticle excitations. We discuss the implications of these results for local quantum criticality and for fundamental bounds on relaxation rates. Drawing on the lessons from these models, we formulate conjectures on coarse grained descriptions of a class of intermediate scale non-fermi liquid behavior in generic correlated metals.
- We show that braidings on a fusion category $\mathcal{C}$ correspond to certain fusion subcategories of the center of $\mathcal{C}$ transversal to the canonical Lagrangian algebra. This allows to classify braidings on non-degenerate and group-theoretical fusion categories.
- Jan 19 2018 cs.LG arXiv:1801.05927v1In this paper we try to organize machine teaching as a coherent set of ideas. Each idea is presented as varying along a dimension. The collection of dimensions then form the problem space of machine teaching, such that existing teaching problems can be characterized in this space. We hope this organization allows us to gain deeper understanding of individual teaching problems, discover connections among them, and identify gaps in the field.
- Jan 18 2018 cs.CV arXiv:1801.05678v1Owe to the rapid development of deep neural network (DNN) techniques and the emergence of large scale face databases, face recognition has achieved a great success in recent years. During the training process of DNN, the face features and classification vectors to be learned will interact with each other, while the distribution of face features will largely affect the convergence status of network and the face similarity computing in test stage. In this work, we formulate jointly the learning of face features and classification vectors, and propose a simple yet effective centralized coordinate learning (CCL) method, which enforces the features to be dispersedly spanned in the coordinate space while ensuring the classification vectors to lie on a hypersphere. An adaptive angular margin is further proposed to enhance the discrimination capability of face features. Extensive experiments are conducted on six face benchmarks, including those have large age gap and hard negative samples. Trained only on the small-scale CASIA Webface dataset with 460K face images from about 10K subjects, our CCL model demonstrates high effectiveness and generality, showing consistently competitive performance across all the six benchmark databases.
- Jan 17 2018 cond-mat.str-el arXiv:1801.05416v1Distinct quantum vacua of topologically ordered states can be tunneled into each other via extended operators. The possible applications include condensed matter and quantum cosmology. We present a straightforward approach to calculate the partition function on various manifolds and ground state degeneracy (GSD), mainly based on continuum/cochain Topological Quantum Field Theories (TQFT), in any dimensions. This information can be related to the counting of extended operators of bosonic/fermionic TQFT. On the lattice scale, anyonic particles/strings live at the ends of line/surface operators. Certain systems in different dimensions are related to each other through dimensional reduction schemes, analogous to decategorification. We consider situations where a TQFT lives on (1) a closed spacetime or (2) a spacetime with boundary, such that both the bulk and boundary are fully-gapped and long-range entangled (LRE). Anyonic excitations can be deconfined on the boundary. We describe such new exotic topological interfaces on which neither particle nor string excitation alone condensed, but only composite objects of extended operators can end (e.g. a string-like composite object formed by a set of particles can end on a special 2+1D boundary of 3+1D bulk). We explore the relations between group extension constructions and partially breaking constructions (e.g. 0-form/higher-form/"composite" breaking) of topological boundaries, after gauging. We comment on the implications of entanglement entropy for some of such LRE systems.
- Jan 17 2018 quant-ph physics.class-ph arXiv:1801.05015v1We present an axiomatic framework for thermodynamics that incorporates information as a fundamental concept. The axioms describe both ordinary thermodynamic processes and those in which information is acquired, used and erased, as in the operation of Maxwell's demon. This system, like previous axiomatic systems for thermodynamics, supports the construction of conserved quantities and an entropy function governing state changes. Here, however, the entropy exhibits both information and thermodynamic aspects. Although our axioms are not based upon probabilistic concepts, a natural and highly useful concept of probability emerges from the entropy function itself. Our abstract system has many models, including both classical and quantum examples.
- A new method to find a lower energy solution to a QUBO/Ising objective function will be presented in this paper. It is applied to samples returned from the D-Wave for various example cases. This method, multi-qubit correction (MQC), creates a sample with an equal-to or less-than energy than any of the D-wave samples used to create it. The method will be detailed and the results of 3 uses cases will be given to demonstrate its merit.
- Jan 16 2018 quant-ph arXiv:1801.04731v1In this article we derive several upper bounds on the quantum capacity of qubit and bosonic thermal attenuators, commonly employed to model the effect of loss and thermal noise in real physical systems and communication processes. We introduce an extended version of such channels which is degradable and hence has a single-letter quantum capacity; the latter is an upper bound for the capacity of the original thermal attenuator channels that is tight in the limit of low thermal noise. For bosonic attenuators we also introduce a further bound based on the bottleneck inequality applied to a particular channel decomposition. With respect to previously known bounds we report better results in a broad range of attenuation and noise values, both for qubit and bosonic attenuators. Even if the exact quantum capacity of thermal attenuators is still unknown, we can now approximate it up to an uncertainty which is negligible for most practical applications.
- In $3d$ Chern-Simons theory, there is a discrete one-form symmetry, whose symmetry group is isomorphic to the center of the gauge group. We study the 't Hooft anomaly associated to this discrete one-form symmetry in theories with generic gauge groups, $A,B,C,D$-types. We propose to detect the discrete anomaly by computing the Hopf state entanglement in the subspace spanned by the symmetry generators and develop a systematical way based on the truncated modular S matrix. We check our proposal for many examples.
- It has been extensively shown in past literature that Bayesian Game Theory and Quantum Non-locality have strong ties between them. Pure Entangled States have been used, in both common and conflict interest games, to gain advantageous payoffs, both at the individual and social level. In this paper we construct a game for a Mixed Entangled State such that this state gives higher payoffs than classically possible, both at the individual level and the social level. Also, we use the I-3322 inequality so that states that aren't helpful as advice for Bell-CHSH inequality can also be used. Finally, the measurement setting we use is a Restricted Social Welfare Strategy (given this particular state).