Search

In this letter, we introduce a fast and computationally efficient iterative algorithm for joint zero diagonalization of a set of complex-valued target matrices. The proposed algorithm is actually a low complexity version of FJZD algorithm, it has a computational complexity of O(K N2), where K and N are the number and dimension of the target matrices respectively. Moreover, the proposed algorithm is superior to FJZD in terms of interference to signal ratio. Simulation results demonstrate the good performance of the proposed algorithm.

As it is well known, for any graph G, we have polynomial-time algorithms to get the classical connectivity κ(G) and edge-connectivity \(\lambda (G)\). However, as we have seen in the last chapter, even for some very special graphs, it is very hard to get the exact values of their generalized k-connectivity for general k. A natural question is whether there is a polynomial-time algorithm to get the parameters κ k (G) and \(\lambda _{k}(G)\). In this chapter, we study the complexity of generalized connectivity.

We perform a mathematical analysis of the classical computational complexity of two genuine quantum-mechanical problems, which are inspired in the calculation of the expected magnetizations and the entanglement between subsystems for a quantum spin system. These problems, which we respectively call SES and SESSP, are specified in terms of pure slightly-entangled quantum states of n qubits, and rigorous mathematical proofs that they belong to the NP-Complete complexity class are presented. Both SES and SESSP are, therefore, computationally equivalent to the relevant 3-SAT problem, for which an efficient algorithm is yet to be discovered., 5 pages

An algorithm complexity, or its efficiency, meaning its time of evaluation is the focus of primary care in algorithmic problems solving. Raising the used memory may reduce the complexity of algorithm drastically. We present an example of two algorithms on finite set, where change the approach to the same problem and introduction a memory array allows decrease the complexity of the algorithm from the order O(n2) up to the order O(n).

In this paper, we analyze the effect of making equivalent transformations for the central path from \( xs=\mu e \) to \( xs=\mu v \), so we obtain a new search direction. For a full-Newton step interior-point algorithm based on this search direction, we have the best known complexity bound is \( \mathrm{ O}(\sqrt{\mathrm{ n}}\ \mathrm{ lon}\varepsilon /\mathrm{ n}) \). Which coincides with the best known iteration bound for feasible interior-point method(IPM). Finally, we concentrate on its numerical implementation where a strategy on the update barrier parameter is made for its numerical performances.

We present a quantum algorithm solving the $k$-distinctness problem in $O(n^{1-2^{k-2}/(2^k-1)})$ queries with a bounded error. This improves the previous $O(n^{k/(k+1)})$-query algorithm by Ambainis. The construction uses a modified learning graph approach. Compared to the recent paper by Belovs and Lee arXiv:1108.3022, the algorithm doesn't require any prior information on the input, and the complexity analysis is much simpler. Additionally, we introduce an $O(\sqrt{n}\alpha^{1/6})$ algorithm for the graph collision problem where $\alpha$ is the independence number of the graph., Comment: 19 pages, 2 figures, major changes

We determine the complexity of several constraint satisfaction problems using the quantum adiabatic algorithm in its simplest implementation. We do so by studying the size dependence of the gap to the first excited state of "typical" instances. We find that at large sizes N, the complexity increases exponentially for all models that we study. We also compare our results against the complexity of the analogous classical algorithm WalkSAT and show that the harder the problem is for the classical algorithm the harder it is also for the quantum adiabatic algorithm., 9 pages, 7 figures

Superposition principle of quantum theory is introduced in this paper. The genetic algorithm has been described by quantum superposition theory. It implies genetic algorithm is essentially a kind of quantum algorithm in the classical computer on the reduced order to achieve. It through genetic manipulation to input superposition states data into classical computer. In the evolutionary process, a lot of implicit modes have been measured, so as to realize the parallel search and processing in the model space. It is implicit parallelism of genetic algorithm. The quantum theory can also be used to analyze the problem?s computational complexity. Quantum superposition theory and entropy are used to get the problem?s lower bound of computational complexity. Using this method the problem?s lower bound of computational complexity is only decided by itself. It is independent of the algorithm?s details.

In this paper, a new algorithm to simplify the Sphere-decoding of V-BLAST architecture is deduced. The system bit error ratio (BER) and complexity are simulated to compare the performance when sphere-decoding algorithm is used with the performance when classical sphere-decoding algorithm is used. According to simulation, the complexity of the modified sphere-decoding algorithm is much lower than the complexity of classical sphere-decoding.

We consider the problem of testing the commutativity of a black-box group specified by its k generators. The complexity (in terms of k) of this problem was first considered by Pak, who gave a randomized algorithm involving O(k) group operations. We construct a quite optimal quantum algorithm for this problem whose complexity is in O(k2/3). The algorithm uses and highlights the power of the quantization method of Szegedy. For the lower bound of Ω(k2/3), we introduce a new technique of reduction for quantum query complexity. Along the way, we prove the optimality of the algorithm of Pak for the randomized model.

In this paper we obtain a new corner cutting algorithm for the evaluation of polynomials represented in the Bernstein-Bezier form. This algorithm has linear time complexity, in contrast to the quadratic time complexity of the usual de Casteljau algorithm.

The Quantum Adiabatic Algorithm has been proposed as a general purpose algorithm for solving hard optimization problems on a quantum computer. Early work on very small sizes indicated that the running time (complexity) only increased as a (quite small) power of the problem size N. We report results of Quantum Monte Carlo simulations, using parallel tempering, with which we determine the minimum energy gap (and hence get information the complexity) for much bigger sizes than was possible before. The aim is to see if there is a “crossover” to exponential complexity at large N. We present data for the typical (median) complexity as a function of N, which indicate a crossover to a first order transition at large sizes. This implies that the complexity is exponential at large N, at least for the problem studied.

The paper addresses the problem of computing the Hyper-Wiener index for molecules in the alkanes family. A new algorithm having linear computational complexity is proposed. The algorithm has optimal complexity, and can be extended to the family of all the acyclic molecular structures. Some computational results are reported.

We compare classical and quantum query complexities of total Boolean functions. It is known that for worst-case complexity, the gap between quantum and classical can be at most polynomial [3]. We show that for average-case complexity under the uniform distribution, quantum algorithms can be exponentially faster than classical algorithms. Under non-uniform distributions the gap can even be super-exponential. We also prove some general bounds for average-case complexity and show that the average-case quantum complexity of MAJORITY under the uniform distribution is nearly quadratically better than the classical complexity.

We compare classical and quantum query complexities of total Boolean functions. It is known that for worst-case complexity, the gap between quantum and classical can be at most polynomial. We show that for average-case complexity under the uniform distribution, quantum algorithms can be exponentially faster than classical algorithms. Under non-uniform distributions the gap can even be super-exponential. We also prove some general bounds for average-case complexity and show that the average-case quantum complexity of MAJORITY under the uniform distribution is nearly quadratically better than the classical complexity., Comment: 14 pages, LaTeX. Some parts rewritten. This version to appear in the Journal of Physics A

The unconstrained domino or tiling problem is the following. Given a finite set T (of tiles), sets H,V ⊑ T×T and a cardinal k ≤ ω, does there exist a function :k×k->T such that (t(i,j),t(i+1,j))eH and (t(i,j),t(i,j+1))eV for all i,j