摘要 :
Grover's algorithm provides a quadratic speedup over classical algorithms to search for marked elements in an unstructured database. The original algorithm is probabilistic, and there are several schemes to achieve the determinist...
展开
Grover's algorithm provides a quadratic speedup over classical algorithms to search for marked elements in an unstructured database. The original algorithm is probabilistic, and there are several schemes to achieve the deterministic version, by using the generalized Grover's iteration G(α,β) := S_r(β)S_o(α). However, in all the existing schemes the value range of α and β is limited; for instance, in the three early schemes they are determined by the proportion of marked states M/N. In this paper, we break through this limitation by presenting a search framework with adjustable parameters, which allows α or β to be arbitrarily given. The significance of the framework lies not only in the expansion of mathematical form, but also in its application value, as we present two disparate problems which we are able to solve deterministically using the proposed framework, whereas previous schemes are ineffective.
收起
摘要 :
Optimization is one of the research areas where quantum computing could bring significant benefits. In this scenario, a hybrid quantum-classical variational algorithm, the Quantum Approximate Optimization Algorithm (QAOA), is rece...
展开
Optimization is one of the research areas where quantum computing could bring significant benefits. In this scenario, a hybrid quantum-classical variational algorithm, the Quantum Approximate Optimization Algorithm (QAOA), is receiving much attention for its potential to efficiently solve combinatorial optimization problems. This approach works by using a classical optimizer to identify appropriate parameters of a problem-dependent quantum circuit, which ultimately performs the optimization process. Unfortunately, learning the most appropriate QAOA circuit parameters is a complex task that is affected by several issues, such as search landscapes characterized by many local optima. Moreover, gradient-based optimizers, which have been pioneered in this context, tend to waste quantum computing resources. Therefore, gradient-free approaches are emerging as promising methods to address this parameter-setting task. Following this trend, this paper proposes, for the first time, the use of genetic algorithms as gradient-free methods for optimizing the QAOA circuit. The proposed evolutionary approach has been evaluated in solving the MaxCut problem for graphs with 5 to 9 nodes on a noisy quantum device. As the results show, the proposed genetic algorithm statistically outperforms the state-of-the-art gradient-free optimizers by achieving solutions with a better approximation ratio.
收起
摘要 :
In this paper, we propose a novel quantum algorithm, based on the Bernstein-Vazirani algorithm, for finding a if the function f (x) = a . pi(x), where a, x is an element of {0, 1}(2) and pi(x) is a 2-bit permutation function. Note...
展开
In this paper, we propose a novel quantum algorithm, based on the Bernstein-Vazirani algorithm, for finding a if the function f (x) = a . pi(x), where a, x is an element of {0, 1}(2) and pi(x) is a 2-bit permutation function. Note that theBernstein-Vazirani algorithm cannot find a when we select the function f (x) = a . pi(x), where pi(x) = ((2013) (0123)). Our algorithm can be further applied to Nagata et al.'s problem. Our algorithm will output g(A(1)) and g(A(0)) if the function f (x) = (g(A(1))g(A(0)))(2) . pi(x), where A(1), A(0) is an element of {0, 1}(m), x is an element of {0, 1}(2) and g : {0, 1}(m) -> {0, 1}.
收起
摘要 :
There exist quantum algorithms that are more efficient than their classical counterparts; such algorithms were invented by Shor in 1994 and then Grover in 1996. A lack of invention since Grover's algorithm has been commonly attrib...
展开
There exist quantum algorithms that are more efficient than their classical counterparts; such algorithms were invented by Shor in 1994 and then Grover in 1996. A lack of invention since Grover's algorithm has been commonly attributed to the non-intuitive nature of quantum algorithms to the classically trained person. Thus, the idea of using computers to automatically generate quantum algorithms based on an evolutionary model emerged. A limitation of this approach is that quantum computers do not yet exist and quantum simulation on a classical machine has an exponential order overhead. Nevertheless, early research into evolving quantum algorithms has shown promise. This paper provides an introduction into quantum and evolutionary algorithms for the computer scientist not familiar with these fields. The exciting field of using evolutionary algorithms to evolve quantum algorithms is then reviewed.
收起
摘要 :
We study quantum walks through chains consisting of two and three star graphs. The first star has a distinguished vertex labelled START and the last has one labelled END. There are multiple paths between these two vertices, and th...
展开
We study quantum walks through chains consisting of two and three star graphs. The first star has a distinguished vertex labelled START and the last has one labelled END. There are multiple paths between these two vertices, and the object is to find these paths. We show that a quantum walk can do this with a quantum speedup.
收起
摘要 :
We analyse the resilience of the quantum search algorithm in the presence of quantum noise modelled as trace preserving completely positive maps. We study the influence of noise on the computational complexity of the quantum searc...
展开
We analyse the resilience of the quantum search algorithm in the presence of quantum noise modelled as trace preserving completely positive maps. We study the influence of noise on the computational complexity of the quantum search algorithm. We show that it is only for small amounts of noise that the quantum search algorithm is still more efficient than any classical algorithm.
收起
摘要 :
We present a quantum deletion algorithm that deletes a marked basis-state from an even superposition of all N basis-states. This algorithm uses only a single query and achieves exponential speed-up compared with classical analog w...
展开
We present a quantum deletion algorithm that deletes a marked basis-state from an even superposition of all N basis-states. This algorithm uses only a single query and achieves exponential speed-up compared with classical analog where __(N) queries are required.
收起
摘要 :
We present a quantum algorithm for fitting a linear regression model to a given data set using the least-squares approach. Differently from previous algorithms which yield a quantum state encoding the optimal parameters, our algor...
展开
We present a quantum algorithm for fitting a linear regression model to a given data set using the least-squares approach. Differently from previous algorithms which yield a quantum state encoding the optimal parameters, our algorithm outputs these numbers in the classical form. So by running it once, one completely determines the fitted model and then can use it to make predictions on new data at little cost. Moreover, our algorithm works in the standard oracle model, and can handle data sets with nonsparse design matrices. It runs in time poly(log_2(N),d,κ,1/ε), where N is the size of the data set, d is the number of adjustable parameters, κ is the condition number of the design matrix, and ε is the desired precision in the output. We also show that the polynomial dependence on d and κ is necessary. Thus, our algorithm cannot be significantly improved. Furthermore, we also give a quantum algorithm that estimates the quality of the least-squares fit (without computing its parameters explicitly). This algorithm runs faster than the one for finding this fit, and can be used to check whether the given data set qualifies for linear regression in the first place.
收起
摘要 :
Abstract Optimization problems are prevalent in various fields, and the gradient-based gradient descent algorithm is a widely adopted optimization method. However, in classical computing, computing the numerical gradient for a fun...
展开
Abstract Optimization problems are prevalent in various fields, and the gradient-based gradient descent algorithm is a widely adopted optimization method. However, in classical computing, computing the numerical gradient for a function with d variables necessitates at least d + 1 function evaluations, resulting in a computational complexity of O(d). As the number of variables increases, the classical gradient estimation methods require substantial resources, ultimately surpassing the capabilities of classical computers. Fortunately, leveraging the principles of superposition and entanglement in quantum mechanics, quantum computers can achieve genuine parallel computing, leading to exponential acceleration over classical algorithms in some cases. In this paper, we propose a novel quantum-based gradient calculation method that requires only a single oracle calculation to obtain the numerical gradient result for a multivariate function. The complexity of this algorithm is just O(1). Building upon this approach, we successfully implemented the quantum gradient descent algorithm and applied it to the variational quantum eigensolver (VQE), creating a pure quantum variational optimization algorithm. Compared with classical gradient-based optimization algorithm, this quantum optimization algorithm has remarkable complexity advantages, providing an efficient solution to optimization problems. The proposed quantum-based method shows promise in enhancing the performance of optimization algorithms, highlighting the potential of quantum computing in this field.
收起
摘要 :
Shor's factoring algorithm (SFA) finds the prime factors of a number, N = p(1)p(2), exponentially faster than the best known classical algorithm. Responsible for the speedup is a subroutine called the quantum order finding algorit...
展开
Shor's factoring algorithm (SFA) finds the prime factors of a number, N = p(1)p(2), exponentially faster than the best known classical algorithm. Responsible for the speedup is a subroutine called the quantum order finding algorithm (QOFA) which calculates the order-the smallest integer, r, satisfying ar mod N = 1, where a is a randomly chosen integer coprime to N (meaning their greatest common divisor is one, gcd(a, N) = 1). Given r, and with probability not <1/2, the factors are given by p(1) = gcd(a(r/2 -1), N) and p(2) = gcd(a(r/2) + 1, N). For odd r, it is assumed that the factors cannot be found (since a(r/2) is not generally integer) and the QOFA is relaunched with a different value of a. But a recent paper (Martin-Lopez et al. Nat. Photonics 6: 773, 2012) noted that the factors can sometimes be found from odd orders if the coprime is square. This raises the question of improving SFA's success probability by considering odd orders. We show that an improvement is possible, though it is small. We present two techniques for retrieving the order from apparently useless runs of the QOFA: not discarding odd orders; and looking out for new order finding relations in the case of failure. In terms of efficiency, using our techniques is equivalent to avoiding square coprimes and disregarding odd orders, which is simpler in practice. Even still, our techniques may be useful in the near future, while demonstrations are restricted to factoring small numbers. The most convincing demonstrations of the QOFA are those that return a non-power-of-two order, making odd orders that lead to the factors attractive to experimentalists.
收起
原文获取