Quantum Algorithms: How Quantum Computers Solve Problems Differently

Angadh Singh

Some problems are computationally solvable but to complexity of nature of problem, they take a long time to solve. Quantum computers (QC) offer the ability to solve these problems in reasonable time using principles of quantum mechanics. One such hard problem is MaxCut, with various applications like portfolio optimization, drug discovery, and inventory management. This poster dives into solving these problems on QC with introduction to how problems are encoded mathematically (QUBO); converted into quantum language (Hamiltonian) and solved using quantum algorithm (QAOA).The goal of research was to run MaxCut problem on different variants of a quantum algorithms to analyze results.

Duong Bui, Kimmo Halunen, Nhan Nguyen +1 more

Noboru Kunihiro, Shigeru Yamashita

No polynomial time algorithms have been proposed for the factoring and discrete logarithm problems.However, Shor showed that these problems can be solved by aquantum Turing machine in 1994.Sev- eral devices have been proposed toward the realization of quantum computers.Among them, the NMR quantum computer seems to be the nearest to the target goal.Since the NMR quantum computer has different features from ordinary ones, we cannot directly implement Shor's algorithms.In this paper, we propose new simple algorithms that work on NMR quantum computers to solve the factoring and discrete logarithm problems.

배준우

Michele Mosca

Elías F. Combarro, Raúl Pérez‐Fernández, José Ranilla +1 more

The aim of a ranking aggregation problem is to combine several rankings into a single one that best represents them. A common method for solving this problem is due to Kemeny and selects as the aggregated ranking the one that minimizes the sum of the Kendall distances to the rankings to be aggregated. Unfortunately, the identification of the said ranking—called the Kemeny ranking—is known to be a computationally expensive task. In this paper, we study different ways of computing the Kemeny ranking with quantum optimization algorithms, and in particular, we provide some alternative formulations for the search for the Kemeny ranking as an optimization problem. To the best of our knowledge, this is the first time that this problem is addressed with quantum techniques. We propose four different ways of formulating the problem, one novel to this work. Two different quantum optimization algorithms—Quantum Approximate Optimization Algorithm and Quantum Adiabatic Computing—are used to evaluate each of the different formulations. The experimental results show that the choice of the formulation plays a big role on the performance of the quantum optimization algorithms.