Can PCE solve the factorisation problem via optimisation?

• URL: http://arxiv.org/abs/2607.23727v1
• Date: Sun, 26 Jul 2026 15:50:43 GMT
• Title: Can PCE solve the factorisation problem via optimisation?
• Abstract summary: integer factorisation remains of special interest due to its relevance to widely used cryptographic schemes such as RSA.<n>One approach to factorisation is to convert the problem into a binary optimisation problem.<n>We investigate a possible adaptation of the Pauli Correlation algorithm to the factorisation problem.
• Score: 40.647387385951816
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The ongoing progress in quantum technologies has fueled a sustained exploration of their potential applications across various domains, particularly in computational problems that are considered intractable for classical systems. Among these problems, integer factorisation remains of special interest due to its relevance to widely used cryptographic schemes such as RSA. Among the different possibilities, one approach to factorisation is to convert the problem into a binary optimisation problem. However, current proposals usually need a large number of qubits that make them unfeasible within the current hardware. In this work, we investigate a possible adaptation of the Pauli Correlation Encoding (PCE) algorithm to the factorisation problem. Due to its compression capability, it can drastically reduce the number of needed qubits. The proposed approach explores how the structure and dynamics of the PCE framework may be employed to encode and analyze candidate factor relations within a quantum computational setting. Rather than presenting a replacement for established quantum factorisation methods, this study aims to provide a preliminary examination of the feasibility and limitations of the proposed adaptation. We discuss the algorithmic design, its conceptual relationship with existing quantum approaches, and the practical constraints associated with implementation on current or near-term quantum hardware. Initial observations suggest that the method may offer an alternative perspective for studying factorisation within the broader context of quantum computation, although no claim is made regarding computational advantage. These results are intended primarily as an exploratory contribution to ongoing research in quantum algorithms and computational number theory.

Related papers

• Quantum computing for genomics: conceptual challenges and practical perspectives [0.0]
  We assess the potential of quantum computing to accelerate computation of central tasks in genomics.<n>We discuss state-of-the-art challenges of quantum search, optimization, and machine learning algorithms.
  arXiv  Detail & Related papers  (2025-07-05T17:41:10Z)
• From Hope to Heuristic: Realistic Runtime Estimates for Quantum Optimisation in NHEP [4.039557813788786]
  Noisy Intermediate-Scale Quantum (NISQ) computers, despite their limitations, present opportunities for near-term quantum advantages in Nuclear and High-Energy Physics.<n>This study focuses on core algorithms that solve optimisation problems through the quadratic Ising or quadratic unconstrained binary optimisation model.
  arXiv  Detail & Related papers  (2025-05-08T08:59:37Z)
• Quantum-Assisted Vehicle Routing: Realizing QAOA-based Approach on Gate-Based Quantum Computer [1.5119440099674915]
  Vehicle Problem Routing (VRP) is a fundamental optimization challenge with broad applications in logistics and transportation.<n>We present a quantum-assisted framework that integrates the Quantum Approximate Optimization Algorithm (QAOA) with a link-based formulation of VRP.<n>Our approach encodes flow conservation and subtour elimination directly into the cost Hamiltonian, preserving graph structure while avoiding ancillary qubits.
  arXiv  Detail & Related papers  (2025-05-02T22:31:01Z)
• Maximizing the practical achievability of quantum annealing attacks on factorization-based cryptography [0.0]
  This work focuses on quantum methods for cryptanalysis of schemes based on the integer factorization problem and the discrete logarithm problem. We demonstrate how to practically solve the largest instances of the factorization problem by improving an approach that combines quantum and classical computations.
  arXiv  Detail & Related papers  (2024-10-07T11:55:23Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [88.57261102552016]
  The anticipated applications of quantum computers span across science and industry.<n>We present a survey of several potential application areas of quantum algorithms.<n>We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Integer Factorization through Func-QAOA [0.0]
  No efficient classical algorithm for cryptographic-time integer factorization has been found. We present the Func-QAOA approach for factorization, which premises overcoming some of the limitations of previous approaches.
  arXiv  Detail & Related papers  (2023-09-26T18:00:25Z)
• Near-Term Distributed Quantum Computation using Mean-Field Corrections and Auxiliary Qubits [77.04894470683776]
  We propose near-term distributed quantum computing that involve limited information transfer and conservative entanglement production. We build upon these concepts to produce an approximate circuit-cutting technique for the fragmented pre-training of variational quantum algorithms.
  arXiv  Detail & Related papers  (2023-09-11T18:00:00Z)
• A Practitioner's Guide to Quantum Algorithms for Optimisation Problems [0.0]
  NP-hard optimisation problems are common in industrial areas such as logistics and finance. This paper aims to provide a comprehensive overview of the theory of quantum optimisation techniques. It focuses on their near-term potential for noisy intermediate scale quantum devices.
  arXiv  Detail & Related papers  (2023-05-12T08:57:36Z)
• 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)
• Synergy Between Quantum Circuits and Tensor Networks: Short-cutting the Race to Practical Quantum Advantage [43.3054117987806]
  We introduce a scalable procedure for harnessing classical computing resources to provide pre-optimized initializations for quantum circuits. We show this method significantly improves the trainability and performance of PQCs on a variety of problems. By demonstrating a means of boosting limited quantum resources using classical computers, our approach illustrates the promise of this synergy between quantum and quantum-inspired models in quantum computing.
  arXiv  Detail & Related papers  (2022-08-29T15:24:03Z)
• Reducing the cost of energy estimation in the variational quantum eigensolver algorithm with robust amplitude estimation [50.591267188664666]
  Quantum chemistry and materials is one of the most promising applications of quantum computing. Much work is still to be done in matching industry-relevant problems in these areas with quantum algorithms that can solve them.
  arXiv  Detail & Related papers  (2022-03-14T16:51:36Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17: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.