Browsing by Author "Liu, Xiaoyuan"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
Item Combinatorial optimization algorithms on quantum and quantum inspired devices(University of Delaware, 2021) Liu, XiaoyuanFrom "quantum-inspired" complementary metal–oxide–semiconductor annealers to universal quantum computers, recent advances in these emerging technologies open the floor for discussions about finding practical applications as well as the specialized algorithms that can utilize such hardware. One of the most promising target applications is the combinatorial optimization. ☐ In this thesis, we first introduce the Ising optimization model, or equivalently, the quadratic unconstrained binary optimization model, a unified mathematical framework that is a target of many special-purpose hardware for optimization. A common limitation of all specialized hardware types is the number of optimization variables that they can handle. ☐ We focus on the problems that are larger than the current hardware size and start our discussion with advocating using a local search framework to create a sequence of sub-problems that can be solved with a limited size hardware. ☐ We introduce the QUBO local search (QUBO-LS), a framework that is, in turn, categorized into two types: constrained QUBO local search (C-QUBO-LS) and unconstrained QUBO local search (U-QUBO-LS). In particular, our U-QUBO-LS addresses the limitations of the QUBO framework and demonstrates efficient use of the hardware by formulating the local search sub-problems into QUBOs that use fewer binary variables and are tailored to the original combinatorial optimization problems. Our U-QUBO-LS can be easily generalized to different combinatorial optimization problems, and we demonstrate local search techniques for the traveling salesman problem (TSP), graph partitioning (GP), quadratic assignment problem (QAP), and minimum 2-sum problem (M2sP) on Ising Processing Units as examples. To further emphasize the generalization of the Ising optimization model, we show another application, namely, the cluster descriptor for the explainability, a problem of major importance in machine learning. We also investigate the performance of current hardware on graph partitioning. ☐ Next, we focus on the combinatorial optimization on near-term universal quantum computers, which is a promising path to demonstrating quantum advantage. However, the capabilities of these devices are constrained by high noise and error rates. We propose an iterative Layer VQE (L-VQE) approach, inspired by the Variational Quantum Eigensolver (VQE). We present a large-scale numerical study, simulating circuits with up to 40 qubits and 352 parameters, that demonstrates the potential of the proposed approach. We evaluate quantum optimization heuristics on the problem of detecting multiple communities in networks, for which we introduce a novel qubit-frugal formulation. We numerically compare L-VQE with the Quantum Approximate Optimization Algorithm (QAOA) and demonstrate that QAOA achieves lower approximation ratios while requiring significantly deeper circuits. We show that L-VQE is more robust to finite sampling errors and has a higher chance of finding the solution as compared with the standard VQE approaches. Our simulation results show that L-VQE performs well under realistic hardware noise. ☐ Finally, we propose to use graph sparsification to reduce the number of quantum circuit gates used in the phase operator of QAOA. Furthermore, if we sparsify the Hamiltonian with an initial suboptimal solution, our sparse QAOA can outperform standard QAOA while using fewer gates and therefore shorter circuit depth. As such, the quantum resources used in QAOA are significantly reduced, making it more possible to execute on near-term noisy quantum devices.Item Quantum computing for finance(Nature Reviews Physics, 2023-07-11) Herman, Dylan; Googin, Cody; Liu, Xiaoyuan; Sun, Yue; Galda, Alexey; Safro, Ilya; Pistoia, Marco; Alexeev, YuriQuantum computers are expected to surpass the computational capabilities of classical computers and have a transformative impact on numerous industry sectors. We present a comprehensive summary of the state of the art of quantum computing for financial applications, with particular emphasis on stochastic modelling, optimization and machine learning. This Review is aimed at physicists, so it outlines the classical techniques used by the financial industry and discusses the potential advantages and limitations of quantum techniques. Finally, we look at the challenges that physicists could help tackle. Key points - Quantum algorithms for stochastic modelling, optimization and machine learning are applicable to various financial problems. - Quantum Monte Carlo integration and gradient estimation can provide quadratic speedup over classical methods, but more work is required to reduce the amount of quantum resources for early fault-tolerant feasibility and achieving an actual speedup. - Financial optimization problems can be continuous (convex or non-convex), discrete or mixed, and thus quantum algorithms for these problems can be applied. - The advantages and challenges of quantum machine learning for classical problems are also apparent in finance.