Quantum computers are designed based on quantum mechanics. They have special features such as entanglement and parallelism, which do not exist in classic mechanics-based computers. Therefore, quantum algorithms have their own privilege for solving some problems compare to classic ones such as finding the minimum value of a function in optimization problems. For instance, finding the minimum of N elements in quantum method is faster than classic method. In this case, having information about N elements of distribution does not reduce the cost of finding the minimum value in classic method due to linear search of each element. But in quantum method, all elements are simultaneously considered as well as distribution information, which is related to the whole elements. This distribution information effectively influences on finding the minimum value. Numerical simulations show having mean and variance of N elements can reduces the cost of minimum finding through quantum method by %40. Furthermore, it is shown the greater variance causes less cost.
Quantum computing is a young but intriguing field of science. It combines quantum mechanics with information theory and computer science to potentially solve certain formerly computationally expensive tasks more efficiently. Classical computers are based on bits that can take on the value zero or one. The values are distinguished by voltage differences in transistors. Quantum computers are instead based on quantum bits, or qubits, that are represented physically by something that exhibits quantum properties, like for example electrons. Qubits also take on the value zero or one, which could correspond to spin up and spin down of an electron. However, qubits can also be in a superposition state between the quantum states corresponding to the value zero and one. This property is what causes quantum computers to be able to outperform classical computers at certain tasks. One of these tasks is searching through an unstructured database. Whereas a classical computer in the worst case has to search through the whole database in order to find the sought element, i.e. the computation time is proportional to the size of the problem, it can be shown that a quantum computer can find the solution in a time proportional to the square root of the size of the problem. This report aims to illustrate the advantages of quantum computing by explicitly solving the classical Windows game Minesweeper, which can be reduced to a problem resembling the unstructured database search problem. It is shown that solving Minesweeper with a quantum algorithm gives a quadratic speedup compared to solving it with a classical algorithm. The report also covers introductory material to quantum mechanics, quantum gates, the particular quantum algorithm Grover's algorithm and complexity classes, which is necessary to grasp in order to understand how Minesweeper can be solved on a quantum computer.
Classical computing there are multiple algorithms to efficiently locate a certain element within a disorganized database; however, quantum computing can be applied more assertively in the face of problems in which it is complicated to verify a solution and at the same time to test multiple and possible solutions. Therefore, this article presents an introduction to Quantum Computing, developing some concepts of quantum formalism, and then approach Grover's algorithm which exploits the principle of superposition to the maximum. Finally, a classic simulation of this algorithm is performed, and the results obtained are compared with classical algorithms such as sequential search and binary search method. A 95% is obtained as a result of greater effectiveness in times -when solving the same search-, revealing the potential advantages of quantum computing.
Finding the minimum value in an unordered database is a common and fundamental task in computer science. However, the optimal classical deterministic algorithm can find the minimum value with a time complexity that grows linearly with the number of elements in the database. In this paper, we present the proposal of a quantum algorithm for finding the minimum value of a database, which is quadratically faster than its best classical analogs. We assume a Quantum Random Access Memory (QRAM) that stores values from a database and perform an iterative search based on an oracle whose role is to limit the searched values by controlling the states of the most significant qubits. A complexity analysis was performed in order to demonstrate the advantage of this quantum algorithm over its classical counterparts. Furthermore, we demonstrate how the proposed algorithm would be used in an unsupervised machine learning task through a quantum version of the K-means algorithm.
Quantum computers have improved and recent experiments have claimed quantum advantage -- completion of a computational task that is evidently hard for any conventional computer. The problem solved is that of obtaining samples, by quantum measurement, from a certain probability distribution. This review shows in what precise way quantum random sampling can be seen as a computation. It explains what that computation solves, in what way it outperforms classical computations, and what methods of verification are available. Quantum random sampling becomes a first test of the presumed exponential computational advantage of quantum computers over classical ones.
This thesis is devoted to four modern quantum optimisation algorithms and their applications. In the first chapter, we provide a complete Quantum Approximate Optimisation Algorithm (QAOA) pipeline for the discrete global minimum-variance portfolio (DGMVP) problem. We introduce an ansatz with efficient initial-state preparation, new hard mixing operators satisfying the constraints of the DGMVP problem, and scalable cost operators utilising binary encoding of the qubits. Benchmarking the method with the most effective optimisation strategies---dual annealing and unfrozen layerwise optimisation---indicates a scaling advantage over classical methods in finding the global optimum of the DGMVP problem. In the second chapter, we show an end-to-end quantum/quantum-inspired Goemans-Williamson semidefinite programming (SDP) method for relaxing Quadratic Unconstrained Binary Optimisation (QUBO) problems and extracting their rounding energy. Our method identifies a class of QUBO instances that is effectively solvable in polylogarithmic time relative to the problem dimension, under the assumptions of Pauli sparsification of the QUBO cost matrix, reducibility of the diagonal constraints, and efficient evaluation of the corresponding Gibbs-state expectation values. Further, we identify the commuting 1D Hamiltonian and the Kronecker graph as practically important instances. Our numerical experiments show that our method solves the SDP and QUBO with up to
250 variables for 1D Hamiltonian instances and achieves results competitive with the best classical solver for Kronecker graphs, giving strong evidence of the power of our algorithm. In the third chapter, we improve the current QAOA method with an iterative warm-start initial-state preparation method. We implement the
t-th order statistic state as the warm-start initial state generated from each QAOA optimisation loop. We achieve an improved approximation ratio when solving the 3-regular MaxCut problem, and find that the worst-case approximation ratio converges to that of the best classical algorithm for
p=1 QAOA. Additionally, our method achieves more favourable scaling than standalone QAOA, single-string warm-started QAOA, and a classical constrained-sampling approach when solving the DGMVP problem. In the fourth chapter, we provide a hard-constrained Grover adaptive search (GAS) method for fixed-sum quadratic binary optimisation problems, and an extension of the alternating direction method of multipliers (ADMM) framework for fixed-sum quartic binary optimisation. Our method guarantees at least a quadratic speed-up over the classical method, and exponentially reduces the gate count for solving fixed-sum binary optimisation when compared with the soft-constrained GAS in the fault-tolerant quantum computing regime. In summary, our contributions include efficient algorithms and novel frameworks that substantially improve performance and broaden the applicability of these quantum optimisation methods. The proposed methods exhibit favourable scaling behaviour and indicate potential quantum advantages in solving challenging optimisation problems, thereby motivating further research at the interface of quantum computing and optimisation.
Quantum computers have the potential to solve Quadratic Unconstrained Binary Optimization (QUBO) problems with lower computational complexity than classical ones. Considering the current limitations of quantum hardware, the joint use of classical and quantum paradigms could exploit both advantages. Quantum routines can make some complex tasks for classical computers feasible. For example, in the Grover Adaptive Search (GAS) procedure, the problem cost function is classically shifted iteratively, whenever a negative value is found through the quantum Grover Search (GS) algorithm, until the minimum is achieved. This quantum-classical approach is characterized by many degrees of freedom, e.g. the number of GS iterations in each call and the stop condition of the algorithm, which should be appropriately tuned for an effective and fast convergence to the optimal solution. The availability of software routines could permit the best management of the GAS parameters. This work proposes new mechanisms for GAS parameters management and compares them with the existing ones, like one available in the Qiskit framework. The proposed mechanisms can automatically arrange the parameters according to the algorithm evolution and their previous experience, thus ensuring a more frequent and faster achievement of the optimal solution. Even though these strategies can be further improved, the results are encouraging. The analysis is done to identify the best policy for different problems. It lays the foundation for designing an automatic toolchain for QUBO solving, which can obtain the best possible implementation of the GAS algorithm for each submitted problem.