اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدBenchmark Study of Quantum Algorithms for Combinatorial Optimization: Unitary versus Dissipative
132
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We study the performance scaling of three quantum algorithms for combinatorial optimization: measurement-feedback coherent Ising machines (MFB-CIM), discrete adiabatic quantum computation (DAQC), and the Durr-Hoyer algorithm for quantum minimum finding (DH-QMF) that is based on Grovers search. We use MaxCut problems as our reference for comparison, and time-to-solution (TTS) as a practical measure of performance for these optimization algorithms. We empirically observe a $Theta(2^{sqrt{n}})$ scaling for the median TTS for MFB-CIM, in comparison to the exponential scaling with the exponent $n$ for DAQC and the provable $widetilde{mathcal O}left(sqrt{2^n}right)$ scaling for DH-QMF. We conclude that these scaling complexities result in a dramatic performance advantage for MFB-CIM in comparison to the other two algorithms for solving MaxCut problems.
قيم البحث
اقرأ أيضاً
The prospect of using quantum computers to solve combinatorial optimization problems via the quantum approximate optimization algorithm (QAOA) has attracted considerable interest in recent years. However, a key limitation associated with QAOA is the
need to classically optimize over a set of quantum circuit parameters. This classical optimization can have significant associated costs and challenges. Here, we provide an expanded description of Lyapunov control-inspired strategies for quantum optimization, as first presented in arXiv:2103.08619, that do not require any classical optimization effort. Instead, these strategies utilize feedback from qubit measurements to assign values to the quantum circuit parameters in a deterministic manner, such that the combinatorial optimization problem solution improves monotonically with the quantum circuit depth. Numerical analyses are presented that investigate the utility of these strategies towards MaxCut on weighted and unweighted 3-regular graphs, both in ideal implementations and also in the presence of measurement noise. We also discuss how how these strategies may be used to seed QAOA optimizations in order to improve performance for near-term applications, and explore connections to quantum annealing.
Emerging quantum processors provide an opportunity to explore new approaches for solving traditional problems in the post Moores law supercomputing era. However, the limited number of qubits makes it infeasible to tackle massive real-world datasets d
irectly in the near future, leading to new challenges in utilizing these quantum processors for practical purposes. Hybrid quantum-classical algorithms that leverage both quantum and classical types of devices are considered as one of the main strategies to apply quantum computing to large-scale problems. In this paper, we advocate the use of multilevel frameworks for combinatorial optimization as a promising general paradigm for designing hybrid quantum-classical algorithms. In order to demonstrate this approach, we apply this method to two well-known combinatorial optimization problems, namely, the Graph Partitioning Problem, and the Community Detection Problem. We develop hybrid multilevel solvers with quantum local search on D-Waves quantum annealer and IBMs gate-model based quantum processor. We carry out experiments on graphs that are orders of magnitudes larger than the current quantum hardware size, and we observe results comparable to state-of-the-art solvers in terms of quality of the solution.
We develop a general method for incentive-based programming of hybrid quantum-classical computing systems using reinforcement learning, and apply this to solve combinatorial optimization problems on both simulated and real gate-based quantum computer
s. Relative to a set of randomly generated problem instances, agents trained through reinforcement learning techniques are capable of producing short quantum programs which generate high quality solutions on both types of quantum resources. We observe generalization to problems outside of the training set, as well as generalization from the simulated quantum resource to the physical quantum resource.
We introduce a quantum divide and conquer algorithm that enables the use of distributed computing for constrained combinatorial optimization problems. The algorithm consists of three major components: classical partitioning of a target graph into mul
tiple subgraphs, variational optimization over these subgraphs, and a quantum circuit cutting procedure that allows the optimization to take place independently on separate quantum processors. We simulate the execution of the quantum divide and conquer algorithm to find approximate solutions to instances of the Maximum Independent Set problem which have nearly twice as many nodes than the number of qubits available on a single quantum processor.
We report a first-principles study of the driven dissipative dynamics for Kerr oscillators in the mesoscopic regime. This regime is characterized by large Kerr nonlinearity, realized here using the nonlinear kinetic inductance of a large array of Jos
ephson junctions. The experimentally measured nonlinear resonance lineshapes of the junction array modes show significant deviations from steady-state numerical predictions, and necessitate time-dependent numerical simulations indicative of strong measurement-induced dephasing in the system arising from the large cross-Kerr effect between array modes. Analytical and numerical calculations of switching rate corroborate this by showing the emergence of a slow time scale, which is much longer than the linear decay rate and is set by fluctuation-induced switching times in the bistable regime. Furthermore, our analysis shows that the usual quantum-activated escape treatment is inadequate for prediction of the switching rates at large frequency shifts caused by strong nonlinearities, necessitating a quantum treatment that utilizes the full system Liouvillian. Based on our analysis, we identify a universal crossover parameter that delineates the regimes of validity of semiclassical and quantum descriptions, respectively. Our work shows how dynamical switching effects in strongly nonlinear systems provide a platform to study quantum-to-classical transitions.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
