Search

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]

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]

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]