Search

Electromagnetic (EM) follow-up observations of gravitational wave events will help shed light on the nature of the sources, and more can be learned if the EM follow-ups can start as soon as the gravitational wave event becomes observable. In this paper, we propose a computationally efficient time-domain algorithm capable of detecting inspirai gravitational waves from coalescing binaries of compact objects with nearly no further delay in addition to the time required to condition the data into a time series of calibrated gravitational-wave strain. Our algorithm, if can be expanded to include sky localization, will serve as the first step towards triggering EM observation before the merger. The key to the efficiency of our algorithm arises from the use of chains of so-called infinite impulse response filters, which filter timeseries data recursively. Computational cost is further reduced by a template interpolation technique that requires filtering only done for a "coarse bank", much sparser than the "fine bank" normally required to sufficiently recover the optimal signal-to-noise ratio: the filter chain of each coarse-bank template is divided into several sections, filtering output from these sections are combined appropriately to reconstruct the output of each of the nearby fine-bank templates. The filter construction and interpolation techniques are illustrated in this paper using Newtonian-chirp waveforms, although these will be generalizable to more accurate post-Newtonian waveforms. Towards future detectors with sensitivity extending to lower frequencies, our algorithm's computational cost is shown to increase rather insignificantly compared to the conventional time-domain correlation method using finite impulse response filters. [ABSTRACT FROM AUTHOR]

For a quantum system controlled by an external field, time-optimal control is referred to as the shortest-time-duration control that can still permit maximizing an objective function J, which is especially a desirable goal for engineering quantum dynamics against decoherence effects. However, since rigorously finding a time-optimal control is usually very difficult and in many circumstances the control is only required to be sufficiently short and precise, one can design algorithms seeking such suboptimal control solutions for much reduced computational effort. In this paper, we propose an iterative algorithm for finding near-time-optimal control in a high level set (i.e., the set of controls that achieves the same value of J) that can be arbitrarily close to the global optima. The algorithm proceeds seeking to decrease the time duration T while the value of J remains invariant, until J leaves the level-set value; the deviation of J due to numerical errors is corrected by gradient climbing that brings the search back to the level-set J value. Since the level set is very close to the maximum value of J, the resulting control solution is nearly time optimal with manageable precision. Numerical examples demonstrate the effectiveness and general applicability of the algorithm. [ABSTRACT FROM AUTHOR]

The one-clean-qubit model of quantum computation (DQC1) efficiently implements a computational task that is not known to have a classical alternative. During the computation, there is never more than a small but finite amount of entanglement present, and it is typically vanishingly small in the system size. In this paper, we demonstrate that there is nothing unexpected hidden within the DQC1 model--Grover's search, when acting on a mixed state, provably exhibits a speedup over classical, with guarantees as to the presence of only vanishingly small amounts of quantum correlations (entanglement and quantum discord)--while arguing that this is not an artifact of the oracle-based construction. We also present some important refinements in the evaluation of how much entanglement may be present in the DQC1 and how the typical entanglement of the system must be evaluated. [ABSTRACT FROM AUTHOR]

Placing signal templates (grid points) as efficiently as possible to cover a multidimensional parameter space is crucial in computing-intensive matched-filtering searches for gravitational waves, but also in similar searches in other fields of astronomy. To generate efficient coverings of arbitrary parameter spaces, stochastic template banks have been advocated, where templates are placed at random while rejecting those too close to others. However, in this simple scheme, for each new random point its distance to every template in the existing bank is computed. This rapidly increasing number of distance computations can render the acceptance of new templates computationally prohibitive, particularly for wide parameter spaces or in large dimensions. This paper presents a neighboring cell algorithm that can dramatically improve the efficiency of constructing a stochastic template bank. By dividing the parameter space into subvolumes (cells), for an arbitrary point an efficient hashing technique is exploited to obtain the index of its enclosing cell along with the parameters of its neighboring templates. Hence only distances to these neighboring templates in the bank are computed, massively lowering the overall computing cost, as demonstrated in simple examples. Furthermore, we propose a novel method based on this technique to increase the fraction of covered parameter space solely by directed template shifts, without adding any templates. As is demonstrated in examples, this method can be highly effective. [ABSTRACT FROM AUTHOR]

As quantum computing technology improves and quantum computers with a small but nontrivial number of N≥100 qubits appear feasible in the near future the question of possible applications of small quantum computers gains importance. One frequently mentioned application is Feynman's original proposal of simulating quantum systems and, in particular, the electronic structure of molecules and materials. In this paper, we analyze the computational requirements for one of the standard algorithms to perform quantum chemistry on a quantum computer. We focus on the quantum resources required to find the ground state of a molecule twice as large as what current classical computers can solve exactly. We find that while such a problem requires about a 10-fold increase in the number of qubits over current technology, the required increase in the number of gates that can be coherently executed is many orders of magnitude larger. This suggests that for quantum computation to become useful for quantum chemistry problems, drastic algorithmic improvements will be needed. [ABSTRACT FROM AUTHOR]

In this paper, we present the first study that compares different models of Bayesian neural networks (BNNs) to predict the posterior distribution of the cosmological parameters directly from the cosmic microwave background (CMB) temperature and polarization maps. We focus our analysis on four different methods to sample the weights of the network during training: Dropout, DropConnect, Reparameterization Trick (RT), and Flipout. We find that Flipout outperforms all other methods regardless of the architecture used, and provides tighter constraints for the cosmological parameters. Moreover, we compare our results with a Markov chain Monte Carlo (MCMC) posterior analysis and obtain comparable error correlations among parameters, with BNNs that are orders of magnitude faster in inference, albeit less accurate. Thanks to the speed of the inference process with BNNs, the posterior distribution--the outcome of the neural network--can be used as the initial proposal for the Markov chain. We show that this combined approach increases the acceptance rate in the Metropolis-Hasting algorithm and accelerates the convergence of the MCMC, while reaching the same final accuracy. In the second part of the paper, we present a guide to the training and calibration of a successful multichannel BNN for the CMB temperature and polarization map. We show how tuning the regularization parameter for the standard deviation of the approximate posterior on the weights in Flipout and RT can produce unbiased and reliable uncertainty estimates, i.e., the regularizer acts like a hyperparameter analogous to the dropout rate in Dropout. The best performances are nevertheless achieved with a more convenient method, in which the network parameters are kept free during training to achieve the best uncalibrated performances, and the confidence intervals are calibrated in a subsequent phase. Additionally, we describe existing strategies for calibrating the networks and propose new ones. Finally, we show how polarization, when combined with the temperature in a unique multichannel tensor fed to a single BNN, helps to break degeneracies among parameters and provides stringent constraints. The results reported in this paper can be extended to other cosmological data sets in order to capture features that can be extracted directly from the raw data, such as non-Gaussianity or foreground emissions. [ABSTRACT FROM AUTHOR]

In this paper we study the identification of the b quark inside a boosted hadronicaliy decaying top quark in the center-of-mass frame of the jet. We demonstrate that the method can be used to greatly reduce the QCD jet background even in a very high pileup condition. The method has a much smaller fake rate for QCD jets compared to typical b quark identification algorithms in jets at the same signal efficiency. When combining the b quark identification in the center-of-mass frame of the jet with jet substructure information, we can improve the rejection rate of QCD jet background by almost an order of magnitude while maintaining the same identification efficiency for the boosted top quark. [ABSTRACT FROM AUTHOR]

The Solovay-Kitaev algorithm is the standard method used for approximating arbitrary single-qubit gates for • fault-tolerant quantum computation. In this paper we introduce a technique called search space expansion, which modifies the initial stage of the Solovay-Kitaev algorithm, increasing the length of the possible approximating sequences but without requiring an exhaustive search over all possible sequences. This technique is combined with an efficient space search method called geometric nearest-neighbor access trees, modified for the unitary matrix lookup problem, in order to reduce significantly the algorithm run time. We show that, with low time cost, our techniques output gate sequences that are almost an order of magnitude smaller for the same level of accuracy. This therefore reduces the error correction requirements for quantum algorithms on encoded fault-tolerant hardware. [ABSTRACT FROM AUTHOR]

Quantum walks are very useful tools in designing quantum algorithms. Amplitude amplification is a key technique to increase the success probability of a quantum-walk-based algorithm, and it is quadratically faster than classical probabilistic amplification. However, amplitude amplification only applies to quantum walks with one-shot hitting time, where no measurements except a final one are performed, and not to quantum walks with concurrent hitting time, where measurements happen or absorbing boundaries exist at each step. In this paper, we propose a procedure to modify quantum walks with concurrent hitting time by removing measurements from them. This procedure enables us to use amplitude amplification to design algorithms based on the modified quantum walks which are faster than those based on the original walks with a concurrent hitting time and more robust than those based on the corresponding walks with a one-shot hitting time. [ABSTRACT FROM AUTHOR]

We present a specific prescription for the calculation of cosmological power spectra, exploited here at two-loop order in perturbation theory, based on the multipoint propagator expansion. In this approach, density and velocity power spectra are constructed from the regularized expressions of the propagators that reproduce both the resummed behavior in the high-k limit and the standard perturbation theory results at low k. With the help of N-body simulations, we particularly focus on the density field, and show that such a construction gives robust and accurate predictions for both the density power spectrum and the correlation function at percent level in the weakly nonlinear regime. We then present an algorithm that allows accelerated evaluations of all the required diagrams by reducing the computational tasks to one-dimensional integrals. This is achieved by means of precomputed kernel sets defined for appropriately chosen fiducial models. The computational time for two-loop results is then reduced from a few minutes, with the direct method, to a few seconds with the fast one. The robustness and applicability of this method are tested against the power spectrum COSMIC EMULATOR from which a wide variety of cosmological models can be explored. The FORTRAN PROGRAM with which direct and fast calculations of density power spectra can be done, REGPT, is publicly released as part of this paper. [ABSTRACT FROM AUTHOR]

In this paper we study the performance of the quantum adiabatic algorithm on random instances of two combinatorial optimization problems, 3-regular 3-XORSAT and 3-regular max-cut. The cost functions associated with these two clause-based optimization problems are similar as they are both defined oh 3-regular hypergraphs. For 3-regular 3-XORSAT the clauses contain three variables and for 3-regular max-cut the clauses contain two variables. The quantum adiabatic algorithms we study for these two problems use interpolating Hamiltonians which are amenable to sign-problem free quantum Monte Carlo and quantum cavity methods. Using these techniques we find that the quantum adiabatic algorithm fails to solve either of these problems efficiently, although for different reasons. [ABSTRACT FROM AUTHOR]

Transient broadband noise in gravitational wave (GW) detectors--also known as noise triggers (referred to as triggers for brevity)--can often be a déterrant to the efficiency with which astrophysical search pipelines detect sources. It is important to understand their instrumental or environmental origin so that they could be eliminated or accounted for in the data. Since the number of triggers is large, data mining approaches such as clustering and classification are useful tools for this task. Classification of triggers based on a handful of discrete properties has been done in the past. A rich information content is available in the waveform or "shape" of the triggers that has had a rather restricted exploration so far. This paper presents a new way to classify triggers deriving information from both trigger waveforms as well as their discrete physical properties, using a sequential combination of the longest common subsequence (LCSS) and LCSS coupled with Fast Time Series Evaluation (FTSE) for waveform classification, and the multidimensional hierarchical classification (MHC) analysis for the grouping based on physical properties. A generalized fc-means algorithm is used with the LCSS (and LCSS + FTSE) for clustering the triggers using a validity measure to determine the correct number of clusters in absence of any prior knowledge. The results have been demonstrated by simulations and by application to a segment of real LIGO data from the sixth science run. [ABSTRACT FROM AUTHOR]

Quantum control landscape theory was formulated to assess the ease of finding optimal control fields in simulations and in the laboratory. The landscape is the observable as a function of the controls, and a primary goal of the theory is the analysis of landscape features. In what is referred to as the kinematic picture of the landscape, prior work showed that the landscapes are generally free of traps that could halt the search for an optimal control at a suboptimal observable value. The present paper considers the dynamical picture of the landscape, seeking the existence of singular controls, especially of a nonkinematic nature along with an assessment of whether they correspond to traps. We analyze the necessary and sufficient conditions for singular controls to be kinematic or nonkinematic critical solutions and the likelihood of their being encountered while maximizing an observable. An algorithm is introduced to seek singular controls on the landscape in simulations along with an associated Hessian landscape analysis. Simulations are performed for a large number of model finite-level quantum systems, showing that all the numerically identified kinematic and nonkinematic singular critical controls are not traps, in support of the prior empirical observations on the ease of finding high-quality optimal control fields. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new approach to study jet substructure in the center-of-mass frame of the jet. We demonstrate that it can be used to discriminate the boosted heavy particles from the QCD jets and the method is complementary to other jet substructure algorithms. Applications to searches for hadronically decaying W/Z + jets and heavy resonances that decay to a WW final state are also discussed. [ABSTRACT FROM AUTHOR]

This paper reports the evaluation of the tenth-order QED contribution to the lepton g -- 2 from the gauge-invariant set of 2072 Feynman diagrams, called Set IV, which are obtained by inserting a second-order lepton vacuum-polarization loop into 518 eighth-order vertex diagrams of four-photon exchange type. The numerical evaluation is carried out by the adaptive-iterative Monte Carlo integration routine VEGAS using the FORTRAN codes written by the automatic code-generating algorithm GENCODEN. Some of the numerical results are confirmed by comparison with the values of corresponding integrals that have been obtained previously by a different method. The result for the mass-independent contribution of the Set IV to the electron g -- 2 is -7.7296(48)(&agr;/&pgr;)5. There is also a small mass-dependent contribution to the electron g - 2 due to the muon loop: -0.01136(7)(&agr;/&pgr;)5. The contribution of the tau-lepton loop is -0.000093 7(104)(&agr;/&pgr;)5. The sum of all these contributions to the electron g - 2 is -7.7407(49) × (&agr;/&pgr;)5. The same set of diagrams enables us to evaluate the contributions to the muon g -- 2 from the electron loop, muon loop, and tau-lepton loop. They add up to --46.95(17)(&agr;/&pgr;)5. [ABSTRACT FROM AUTHOR]

In this paper, we systematically study property testing of unitary operators. We first introduce a distance measure that reflects the average difference between unitary operators. Then we show that, with respect to this distance measure, the orthogonal group, quantum juntas (i.e., unitary operators that only nontrivially act on a few qubits of the system), and the Clifford group can be all efficiently tested. In fact, their testing algorithms have query complexities independent of the system's size and have only one-sided error. Then we give an algorithm that tests any finite subset of the unitary group, and demonstrate an application of this algorithm to the permutation group. This algorithm also has one-sided error and polynomial query complexity, but it is unknown whether it can be efficiently implemented in general. [ABSTRACT FROM AUTHOR]

Despite early experimental tests of the Deutsch-Jozsa (DJ) algorithm, there have been only a very few nontrivial balanced functions tested for register number n > 3. In this paper, we experimentally demonstrate the DJ algorithm in four- and five-qubit homonuclear spin systems by the nuclear-magnetic-resonance technique, by which we encode the one function evaluation into a long shaped pulse with the application of the gradient ascent algorithm. Our work, dramatically reducing the accumulated errors due to gate imperfections and relaxation. demonstrates a better implementation of the DJ algorithm. [ABSTRACT FROM AUTHOR]

Quantum walks are interesting models with potential applications to quantum algorithms and physical processes such as photosynthesis. In this paper, we study two models of one-dimensional quantum walks, namely, quantum walks with a moving absorbing wall and quantum walks with one stationary and one moving absorbing wall. For the former, we calculate numerically the survival probability, the rate of change of average position, and the rate of change of standard deviation of the particle's position in the long time limit for different wall velocities. Moreover, we also study the asymptotic behavior and the dependence of the survival probability on the initial particle's state. While for the latter, we compute the absorption probability of the right stationary wall for different velocities and initial positions of the left wall boundary. The results for these two models are compared with those obtained for the classical model. The difference between the results obtained for the quantum and classical models can be attributed to the difference in the probability distributions. [ABSTRACT FROM AUTHOR]

In this paper we report a measurement of the tt̄ production cross section in pp̄ collisions at √s = 1.96 TeV using data corresponding to an integrated luminosity of 2.2 fb-1 collected with the CDF II detector at the Tevatron accelerator. We select events with significant missing transverse energy and high jet multiplicity. This measurement vetoes the presence of explicitly identified electrons and muons, thus enhancing the tau contribution of tt̄ decays. Signal events are discriminated from the background using a neural network, and heavy flavor jets are identified by a secondary-vertex tagging algorithm. We measure a tt̄ production cross section of 7.99 ± 0.55(stat) ± 0.76(syst) ± 0.46(lumi) pb, assuming a top mass mtop = 172.5 GeV/c², in agreement with previous measurements and standard model predictions. [ABSTRACT FROM AUTHOR]

Quantum convolutional codes, like their classical counterparts, promise to offer higher error correction performance than block codes of equivalent encoding complexity, and are expected to find important applications in reliable quantum communication where a continuous stream of qubits is transmitted. Grassl and Roetteler devised an algorithm to encode a quantum convolutional code with a "pearl-necklace" encoder. Despite their algorithm's theoretical significance as a neat way of representing quantum convolutional codes, it is not well suited to practical realization. In fact, there is no straightforward way to implement any given pearl-necklace structure. This paper closes the gap between theoretical representation and practical implementation. In our previous work, we presented an efficient algorithm to find a minimal-memory realization of a pearl-necklace encoder for Calderbank-Shor-Steane (CSS) convolutional codes. This work is an extension of our previous work and presents an algorithm for turning a pearl-necklace encoder for a general (non-CSS) quantum convolutional code into a realizable quantum convolutional encoder. We show that a minimal-memory realization depends on the commutativity relations between the gate strings in the pearl-necklace encoder. We find a realization by means of a weighted graph which details the noncommutative paths through the pearl necklace. The weight of the longest path in this graph is equal to the minimal amount of memory needed to implement the encoder. The algorithm has a polynomial-time complexity in the number of gate strings in the pearl-necklace encoder. [ABSTRACT FROM AUTHOR]

In this paper, we generalize Jordan-Lee-Preskill, an algorithm for simulating flat-space quantum field theories, to 3 + 1 dimensional inflationary spacetime. The generalized algorithm contains the encoding treatment, the initial state preparation, the inflation process, and the quantum measurement of cosmological observables at late time. The algorithm is helpful for obtaining predictions of cosmic non-Gaussianities, serving as useful benchmark problems for quantum devices, and checking assumptions made about interacting vacuum in the inflationary perturbation theory. Components of our work also include a detailed discussion about the lattice regularization of the cosmic perturbation theory, a detailed discussion about the in-in formalism, a discussion about encoding using the Hamilton-Kabat-Lifschytz-Lowe-type formula that might apply for both dS and AdS spacetimes, a discussion about bounding curvature perturbations, a description of the three-party Trotter simulation algorithm for time-dependent Hamiltonians, a ground state projection algorithm for simulating gapless theories, a discussion about the quantum-extended Church-Turing thesis, and a discussion about simulating cosmic reheating in quantum devices. [ABSTRACT FROM AUTHOR]

Efficient and stable algorithms for the calculation of spectral quantities and correlation functions are some of the key tools in computational condensed-matter physics. In this paper basic properties and recent developments of Chebyshev expansion based algorithms and the kernel polynomial method are reviewed. Characterized by a resource consumption that scales linearly with the problem dimension these methods enjoyed growing popularity over the last decade and found broad application not only in physics. Representative examples from the fields of disordered systems, strongly correlated electrons, electron-phonon interaction, and quantum spin systems are discussed in detail. In addition, an illustration on how the kernel polynomial method is successfully embedded into other numerical techniques, such as cluster perturbation theory or Monte Carlo simulation, is provided. [ABSTRACT FROM AUTHOR]

The physics of high-energy colliders relies on the knowledge of different nonperturbative parton correlators, such as parton distribution functions, that encode the information on universal hadron structure and are thus the main building blocks of any factorization theorem of the underlying process in such collision. These functions are given in terms of gauge-invariant light-front operators, that are nonlocal in both space and real time, and thus intractable by standard lattice techniques due to the well-known sign problem. In this paper, we propose a quantum algorithm to perform a quantum simulation of these type of correlators, and illustrate it by considering a space-time Wilson loop. We discuss the implementation of the quantum algorithm in terms of quantum gates that are accessible within actual quantum technologies such as cold atoms setups, trapped ions or superconducting circuits. [ABSTRACT FROM AUTHOR]

The simulation of dense fermionic matters is a long-standing problem in lattice gauge theory. One hopeful solution would be the use of quantum computers. In this paper, digital quantum simulation is designed for lattice gauge theory at nonzero density. The quantum variational algorithm is adopted to obtain the ground state at nonzero density. A benchmark test is performed in the lattice Schwinger model. [ABSTRACT FROM AUTHOR]

The Laser Interferometer Space Antenna (LISA) is a European Space Agency mission that aims to measure gravitational waves in the millihertz range. The three-spacecraft constellation forms a nearly equilateral triangle, which experiences flexing along its orbit around the Sun. These time-varying and unequal armlengths require to process measurements with time-delay interferometry (TDI) to synthesize virtual equal-arm interferometers, and reduce the otherwise overwhelming laser frequency noise. Algorithms compatible with such TDI combinations have recently been proposed in order to suppress the phase fluctuations of the onboard ultra-stable oscillators (USO) used as reference clocks. In this paper, we propose a new method to cancel USO noise in TDI combinations. This method has comparable performance to existing algorithms, but is more general as it can be applied to most TDI combinations found in the literature. We compute analytical expressions for the residual clock noise before and after correction, accounting for the effect of time-varying beatnote frequencies, previously neglected. We present results of numerical simulations that are in agreement with our models, and show that clock noise can be suppressed below required levels. The suppression algorithm introduces a new modulation noise, for which we propose a partial mitigation. This modulation noise remains the limiting effect for clock-noise suppression, setting strict timing requirements on the sideband generation. [ABSTRACT FROM AUTHOR]

In this paper we apply a recently proposed numerical algorithm for finding stationary phase points in spin foam amplitudes. We study a spin foam amplitude with three vertices and a bulk face in 4D BF theory. We fix the boundary coherent states to three possible triangulations, one with zero deficit angle on the bulk face and two with nonzero deficit angle. We compute the amplitude numerically and we find a stationary phase point already at low spins in all the three cases. We comment on how this result contrasts with the claims of flatness problem in spin foam theories. We point out where these arguments may be misleading and we propose further computations to definitively answer the question. [ABSTRACT FROM AUTHOR]

Quantum search on the two-dimensional lattice with one marked vertex and cyclic boundary conditions is an important problem in the context of quantum algorithms with an interesting unfolding. It avails to test the ability of quantum walk models to provide efficient algorithms from the theoretical side and means to implement quantum walks in laboratories from the practical side. In this paper, we rigorously prove that the recent-proposed staggered quantum walk model provides an efficient quantum search on the two-dimensional lattice, if the reflection operators associated with the graph tessellations are used as Hamiltonians, which is an important theoretical result for validating the staggered model with Hamiltonians. Numerical results show that on the two-dimensional lattice staggered models without Hamiltonians are not as efficient as the one described in this paper and are, in fact, as slow as classical random-walk-based algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we study the pseudo-Wigner solution of the quark gap equation with a recently proposed algorithm in the framework of the (2+1)-flavor Nambu-Jona-Lasinio (NJL) model. We find that for the current quark mass mu,d=5.5=MeV and chemical potential μ<μTCP=272.5=MeV, the Nambu solution and the positive pseudo-Wigner solution obtained via this algorithm is consistent with the physical solution obtained with the iterative method. Furthermore, the algorithm we used can help to illustrate the evolution of the solutions of the gap equation from the chiral limit to nonchiral limit and gives a prediction where the crossover line is located in the phase diagram for μ<272.5=MeV. In addition, we also study the chiral susceptibilities as well as the loss of solutions for different chemical potentials. [ABSTRACT FROM AUTHOR]

Recently, a series of papers by Combes et al. [J. Combes, H. M. Wiseman, and K. Jacobs, Phys. Rev. Lett. 100, 160503 (2008); J. Combes, H. M. Wiseman, and A. J. Scott, Phys. Rev. A 81, 020301(R) (2010); J. Combes and H. M. Wiseman, Phys. Rev. X 1, 011012 (2011); J. Combes, A. Denney, and H. M. Wiseman, Phys. Rev. A 91, 022305 (2015)] has shown that it is possible to greatly improve the measurement rate of a register of qubits for given detector resources by means of a clever feedback control scheme. However, this speedup came at an exponential cost in terms of complexity and memory use. In this paper, I propose a simple efficient algorithm--exponentially more frugal in memory and less complex to implement--which is asymptotically as fast. I use extensively the implicit classicality of the situation to provide a slightly more straightforward interpretation of the results. I compute the speedup rates exactly in the case of the proposed model and in the case of the open-loop scheme of Combes et al. and prove that they indeed provide the same asymptotic speedup. [ABSTRACT FROM AUTHOR]

In this paper, we prove that KG(3)

Causal discovery algorithms allow for the inference of causal structures from probabilistic relations of random variables. A natural field for the application of this tool is quantum mechanics, where a long-standing debate about the role of causality in the theory has flourished since its early days. In this paper, a causal discovery algorithm is applied in the search for causal models to describe a quantum version of Wheeler's delayed-choice experiment. The outputs explicitly show the restrictions for the introduction of classical concepts in this system. The exclusion of models with two hidden variables is one of them. A consequence of such a constraint is the impossibility to construct a causal model that avoids superluminal causation and assumes an objective view of the wave and particle properties simultaneously. [ABSTRACT FROM AUTHOR]

The traveling-salesman problem is one of the most famous problems in graph theory. However, little is currently known about the extent to which quantum computers could speed up algorithms for the problem. In this paper, we prove a quadratic quantum speedup when the degree of each vertex is at most 3 by applying a quantum backtracking algorithm to a classical algorithm by Xiao and Nagamochi. We then use similar techniques to accelerate a classical algorithm for when the degree of each vertex is at most 4, before speeding up higher-degree graphs via reductions to these instances. [ABSTRACT FROM AUTHOR]

A two-party quantum communication process with classical inputs and outcomes can be simulated by replacing the quantum channel with a classical one. The minimal amount of classical communication required to reproduce the statistics of the quantum process is called its communication complexity. In the case of many instances simulated in parallel, the minimal communication cost per instance is called the asymptotic communication complexity. Previously, we reduced the computation of the asymptotic communication complexity to a convex minimization problem. In most cases, the objective function does not have an explicit analytic form, as the function is defined as the maximum over an infinite set of convex functions. Therefore, the overall problem takes the form of a minimax problem and cannot directly be solved by standard optimization methods. In this paper, we introduce a simple algorithm to compute the asymptotic communication complexity. For some special cases with an analytic objective function one can employ available convex-optimization libraries. In the tested cases our method turned out to be notably faster. Finally, using our method we obtain 1.238 bits as a lower bound on the asymptotic communication complexity of a noiseless quantum channel with the capacity of 1 qubit. This improves the previous bound of 1.208 bits. [ABSTRACT FROM AUTHOR]