Search NASA⌕ Search

Engineering topics

Lykov, Danylo

Publications and source records attributed to Lykov, Danylo.

Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem

The quantum approximate optimization algorithm (QAOA) is a leading candidate algorithm for solving optimization problems on quantum computers. However, the potential of QAOA to tackle classically intractable problems remains unclear. Here, we perform an extensive numerical investigation of QAOA on the low autocorrelation binary sequences (LABS) problem, which is classically intractable even for moderately sized instances. We perform noiseless simulations with up to 40 qubits and observe that the runtime of QAOA with fixed parameters scales better than branch-and-bound solvers, which are the state-of-the-art exact solvers for LABS. The combination of QAOA with quantum minimum finding gives the best empirical scaling of any algorithm for the LABS problem. We demonstrate experimental progress in executing QAOA for the LABS problem using an algorithm-specific error detection scheme on Quantinuum trapped-ion processors. Our results provide evidence for the utility of QAOA as an algorithmic component that enables quantum speedups.

97 MATHEMATICS AND COMPUTING↗

Sampling frequency thresholds for the quantum advantage of the quantum approximate optimization algorithm

We compare the performance of the Quantum Approximate Optimization Algorithm (QAOA) with state-of-the-art classical solvers Gurobi and MQLib to solve the MaxCut problem on 3-regular graphs. We identify the minimum noiseless sampling frequency and depth p required for a quantum device to outperform classical algorithms. There is potential for quantum advantage on hundreds of qubits and moderate depth with a sampling frequency of 10 kHz. We observe, however, that classical heuristic solvers are capable of producing high-quality approximate solutions in linear time complexity. In order to match this quality for large graph sizes N, a quantum device must support depth p > 11. Additionally, multi-shot QAOA is not efficient on large graphs, indicating that QAOA p ≤ 11 does not scale with N. These results limit achieving quantum advantage for QAOA MaxCut on 3-regular graphs. Other problems, such as different graphs, weighted MaxCut, and 3-SAT, may be better suited for achieving quantum advantage on near-term quantum devices.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Embedding Learning in Hybrid Quantum-Classical Neural Networks

Quantum embedding learning is an important step in the application of quantum machine learning to classical data. In this paper we propose a quantum few-shot embedding learning paradigm, which learns embeddings useful for training downstream quantum machine learning tasks. Crucially, we identify the circuit bypass problem in hybrid neural networks, where learned classical parameters are optimized to represent the dataset without the quantum kernel. We observe that the few-shot learning embeddings generalize to unseen classes, and suffer less from the circuit bypass problem in terms of better occupation of the parameter space compared with embeddings learned from regression and classification.

Liu, Minzhao↗

Fixed-angle conjectures for the quantum approximate optimization algorithm on regular MaxCut graphs

The quantum approximate optimization algorithm (QAOA) is a near-term combinatorial optimization algorithm suitable for noisy quantum devices. However, little is known about performance guarantees for p > 2. A recent work computing MaxCut performance guarantees for 3-regular graphs conjectures that any d-regular graph evaluated at particular fixed angles has an approximation ratio greater than some worst-case guarantee. In this work, we provide numerical evidence for this fixed angle conjecture for p < 12. We compute and provide these angles via numerical optimization and tensor networks. These fixed angles serve for an optimization-free version of QAOA and have universally good performance on any 3-regular graph. Heuristic evidence is presented for the fixed angle conjecture on graph ensembles, which suggests that these fixed angles are "close" to global optimum. Under the fixed angle conjecture, QAOA has a larger performance guarantee than the Goemans Williamson algorithm on 3-regular graphs for p >= 11.

Wurtz, Jonathan↗

QTENSOR

QTensor is a quantum circuit simulator designed to run efficiently in parallel mode on large supercomputers. It is based on the tensor network representation of quantum circuits. The simulator is flexible and agnostic to both the connectivity map of the quantum device and the types of gates used in the circuit.

Alekseev, Yury↗

Proxy App Suite Release (FY2020)

Version 4.0 of the ECP Proxy App Suite is practically unchanged from the previous release. The current set of proxies has proven useful for many aspects of benchmarking and co-design and we see little reason to alter the suite. Although there have been few changes to the ECP suite, the team has been hard at work in other areas. In the area of Machine Learning (ML) we have now created a separate proxy suite dedicated to this scientific applications of ML.

97 MATHEMATICS AND COMPUTING↗

FY20 Proxy App Suite Release: Report for ECP Proxy App Project Milestone ADCD-504-10

Version 4.0 of the ECP Proxy App Suite is practically unchanged from the previous release. The current set of proxies has proven useful for many aspects of benchmarking and co-design and we see little reason to alter the suite. Although there have been few changes to the ECP suite, the team has been hard at work in other areas. In the area of Machine Learning (ML) we have now created a separate proxy suite dedicated to this scientific applications of ML. The suite includes: miniGAN (Generative Adversarial Networks), miniRL (Reinforcement Learning), CRADL (inline inference), Cosmoflow-Benchmark (Convolutional Neural Network), and MLPerf-DeepCam (Climate Segmentation Benchmark). Section 3 contains more information about these proxies as well as the principles that are guiding the development of the suite. We have surveyed available proxies for several application domains including Computational Fluid Dynamics, Quantum Chemistry, Quantum Computing Simulation, Molecular Dynamics, Monte Carlo Transport, and Density Functional Theory to identify gaps in proxy coverage. Several new proxy apps are either already available or will be released soon to fill these gaps. Section 4 provides full details. Finally, section 5 reports on our continued collaboration with the ECP Continuous Integration (CI) effort to use proxy apps to help identify problems and roadblocks to cross-lab CI. We have also assisted the El Capitan Center of Excellence (COE) to stand up a CI system that will be used to test releases of HPE and AMD software stacks. We hope that the COE effort can serve as a model for ECP by showing how the Proxy App Team can work with AD and ST teams identify critical features, kernels, patterns, etc. and incorporate them into a CI system that will help ensure that Frontier and Aurora will provide those needed capabilities.

97 MATHEMATICS AND COMPUTING↗