Hard instance learning for quantum adiabatic prime factorization

• URL: http://arxiv.org/abs/2110.04782v1
• Date: Sun, 10 Oct 2021 12:51:31 GMT
• Title: Hard instance learning for quantum adiabatic prime factorization
• Authors: Jian Lin, Zhengfeng Zhang, Junping Zhang, Xiaopeng Li
• Abstract summary: Prime factorization is the foundation of Rivest-Shamir-Adleman (RSA) cryptography. With programmable quantum devices, adiabatic quantum computing has been proposed as a plausible approach to solve prime factorization.
• Score: 21.615348663035846
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Prime factorization is a difficult problem with classical computing, whose exponential hardness is the foundation of Rivest-Shamir-Adleman (RSA) cryptography. With programmable quantum devices, adiabatic quantum computing has been proposed as a plausible approach to solve prime factorization, having promising advantage over classical computing. Here, we find there are certain hard instances that are consistently intractable for both classical simulated annealing and un-configured adiabatic quantum computing (AQC). Aiming at an automated architecture for optimal configuration of quantum adiabatic factorization, we apply a deep reinforcement learning (RL) method to configure the AQC algorithm. By setting the success probability of the worst-case problem instances as the reward to RL, we show the AQC performance on the hard instances is dramatically improved by RL configuration. The success probability also becomes more evenly distributed over different problem instances, meaning the configured AQC is more stable as compared to the un-configured case. Through a technique of transfer learning, we find prominent evidence that the framework of AQC configuration is scalable -- the configured AQC as trained on five qubits remains working efficiently on nine qubits with a minimal amount of additional training cost.

Related papers

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Single entanglement connection architecture between multi-layer bipartite Hardware Efficient Ansatz [18.876952671920133]
  We propose a single entanglement connection architecture (SECA) for a bipartite hardware efficient ansatz. Our results indicate the superiority of SECA over the common full entanglement connection architecture (FECA) in terms of computational performance.
  arXiv  Detail & Related papers  (2023-07-23T13:36:30Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• QNEAT: Natural Evolution of Variational Quantum Circuit Architecture [95.29334926638462]
  We focus on variational quantum circuits (VQC), which emerged as the most promising candidates for the quantum counterpart of neural networks. Although showing promising results, VQCs can be hard to train because of different issues, e.g., barren plateau, periodicity of the weights, or choice of architecture. We propose a gradient-free algorithm inspired by natural evolution to optimize both the weights and the architecture of the VQC.
  arXiv  Detail & Related papers  (2023-04-14T08:03:20Z)
• Asynchronous training of quantum reinforcement learning [0.8702432681310399]
  A leading method of building quantum RL agents relies on the variational quantum circuits (VQCs) In this paper, we approach this challenge through asynchronous training QRL agents. We demonstrate the results via numerical simulations that within the tasks considered, the asynchronous training of QRL agents can reach performance comparable to or superior.
  arXiv  Detail & Related papers  (2023-01-12T15:54:44Z)
• Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
  We propose a Reinforcement Learning (RL) approach combined with Graph Neural Networks (GNN) to address the contraction ordering problem. The problem is extremely challenging due to the huge search space, the heavy-tailed reward distribution, and the challenging credit assignment. We show how a carefully implemented RL-agent that uses a GNN as the basic policy construct can address these challenges.
  arXiv  Detail & Related papers  (2022-04-18T21:45:13Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Quantum Architecture Search via Continual Reinforcement Learning [0.0]
  This paper proposes a machine learning-based method to construct quantum circuit architectures. We present the Probabilistic Policy Reuse with deep Q-learning (PPR-DQL) framework to tackle this circuit design challenge.
  arXiv  Detail & Related papers  (2021-12-10T19:07:56Z)
• Reducing Unitary Coupled Cluster Circuit Depth by Classical Stochastic Amplitude Pre-Screening [0.0]
  Unitary Coupled Cluster (UCC) approaches are an appealing route to utilising quantum hardware to perform quantum chemistry calculations. We present a combined classical-quantum approach where a classical UCC pre-processing step is used to determine the important excitations in the UCC ansatz.
  arXiv  Detail & Related papers  (2021-08-24T18:34:14Z)
• Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
  We propose a resource and runtime efficient scheme termed quantum architecture search (QAS) QAS automatically seeks a near-optimal ansatz to balance benefits and side-effects brought by adding more noisy quantum gates. We implement QAS on both the numerical simulator and real quantum hardware, via the IBM cloud, to accomplish data classification and quantum chemistry tasks.
  arXiv  Detail & Related papers  (2020-10-20T12:06:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.