Hybrid Number Field Sieve (NFS): Classical and Quantum approaches

Inhaltsverzeichnis (Table of Contents)

• 1 Introduction
• 1.1 Integer factorization: classical, quantum and hybrid approaches
• 1.2 Problem statement: Quantum annealers and hybrid NFS algorithm for integer factorization
• 1.3 Scientific Approach, Investigative Method and Results
• 1.4 Contents of this report
• 2 Integer factorization with Quantum Annealing
• 2.1 Introduction
• 2.2 Quantum annealing in D-Wave systems
• 2.2.1 The physics behind quantum annealing
• 2.3 Problem formulation
• 2.3.1 Ising and QUBO
• 2.3.2 Minor-Embedding
• 2.4 Embedding notion
• 2.5 Parameter setting
• 2.6 D-Wave Example
• 2.6.1 Defining a simple problem
• 2.6.2 Representing contraints with QUBO
• 2.6.3 Convert the QUBO model into a graph
• 2.6.4 Minor-Embedding the problem into the Chimera graph
• 2.6.5 Map the problem parameters to the working graph
• 2.6.6 Unembeding the solution
• 2.7 Results for other arbitrary values of the coupler strength
• 2.7.1 From a triangular graph to a hexagon
• 2.8 Integer factorization using Quantum Annealers
• 2.8.1 Factoring 35 as a toy example
• 2.8.2 Simplifying the model
• 2.8.3 Further simplifications
• 2.9 Methods
• 2.9.1 D-Wave Tools
• 3 Using quantum SAT solvers to speed up factoring
• 3.1 Introduction
• 3.2 The Number Field Sieve
• 3.3 SAT circuits
• 3.3.1 Circuits with variable exponents
• 3.3.2 Using factors as variables
• 3.3.3 The Elliptic Curve Method circuit
• 3.4 Future possibilities

Zielsetzung und Themenschwerpunkte (Objectives and Key Themes)

This research project investigates hybrid approaches to integer factorization, combining classical and quantum computing methods. The primary objective is to explore the application of quantum annealing and quantum SAT solvers to improve the efficiency of the Number Field Sieve (NFS) algorithm, currently the best classical algorithm for factoring large integers. The project aims to compare these approaches at a low level, considering both number theory and algorithmic optimizations.

• Hybrid approaches to integer factorization
• Application of quantum annealing to the NFS algorithm
• Utilization of quantum SAT solvers for NFS speedup
• Comparative analysis of different quantum-classical hybrid methods
• Low-level optimization techniques in hybrid quantum-classical algorithms

Zusammenfassung der Kapitel (Chapter Summaries)

1 Introduction: This introductory chapter sets the stage for the research by outlining the current state of integer factorization algorithms, both classical (like the Number Field Sieve) and quantum (Shor's algorithm). It highlights the limitations of fully quantum approaches due to the technological hurdles in building large-scale fault-tolerant quantum computers. The chapter introduces the concept of hybrid approaches combining classical and quantum computing for integer factorization and briefly describes the specific hybrid approaches explored in the research—using quantum annealers and quantum SAT solvers—before outlining the structure of the report.

2 Integer factorization with Quantum Annealing: This chapter delves into the utilization of quantum annealing, specifically using D-Wave systems, for integer factorization. It begins with an explanation of quantum annealing and its underlying physics, followed by a detailed explanation of problem formulation in terms of Ising models and Quadratic Unconstrained Binary Optimization (QUBO). The chapter describes the process of embedding the problem onto the D-Wave's Chimera graph architecture, including parameter setting and minor embedding techniques. A significant part focuses on a practical example of factoring 35, including the simplifications applied to reduce the number of qubits required. The chapter also presents results and discusses methods used, especially the D-Wave tools employed.

3 Using quantum SAT solvers to speed up factoring: This chapter explores a different hybrid approach, focusing on the use of quantum SAT solvers to accelerate the Number Field Sieve. It starts with an introduction to the Number Field Sieve and then dives into the construction of SAT circuits relevant to integer factorization. Different types of SAT circuits are discussed, including those using variable exponents and those representing factors as variables. The chapter briefly mentions the application of this approach to the Elliptic Curve Method and concludes by looking at potential future developments and avenues for further research in this area. This chapter contrasts the quantum annealing approach detailed in Chapter 2 by focusing on a different method of incorporating quantum computation into the overall process of factoring numbers.

Schlüsselwörter (Keywords)

Integer factorization, Number Field Sieve (NFS), quantum computing, quantum annealing, D-Wave, quantum SAT solvers, hybrid algorithms, Ising model, QUBO, minor embedding, Shor's algorithm, classical algorithms, algorithmic optimization.

Häufig gestellte Fragen

What is the primary focus of this document?

This document is a language preview for research on hybrid approaches to integer factorization, specifically combining classical algorithms like the Number Field Sieve (NFS) with quantum computing techniques such as quantum annealing and quantum SAT solvers.

What are the main objectives of the research described in this language preview?

The main objectives are to explore the application of quantum annealing and quantum SAT solvers to improve the efficiency of the Number Field Sieve (NFS) algorithm, compare these hybrid approaches at a low level, and consider both number theory and algorithmic optimizations.

What are the key themes explored in this research?

The key themes include hybrid approaches to integer factorization, application of quantum annealing to the NFS algorithm, utilization of quantum SAT solvers for NFS speedup, comparative analysis of different quantum-classical hybrid methods, and low-level optimization techniques in hybrid quantum-classical algorithms.

What does Chapter 1 cover?

Chapter 1 introduces integer factorization algorithms, both classical (NFS) and quantum (Shor's algorithm), and discusses the limitations of fully quantum approaches. It introduces the concept of hybrid approaches and describes the specific hybrid approaches explored in the research.

What is the focus of Chapter 2?

Chapter 2 focuses on using quantum annealing, specifically using D-Wave systems, for integer factorization. It explains quantum annealing, problem formulation in terms of Ising models and QUBO, embedding the problem onto the D-Wave architecture, and includes a practical example of factoring 35.

What is the subject of Chapter 3?

Chapter 3 explores using quantum SAT solvers to accelerate the Number Field Sieve. It discusses the construction of SAT circuits relevant to integer factorization and different types of SAT circuits.

What are some of the keywords associated with this research?

Keywords include: Integer factorization, Number Field Sieve (NFS), quantum computing, quantum annealing, D-Wave, quantum SAT solvers, hybrid algorithms, Ising model, QUBO, minor embedding, Shor's algorithm, classical algorithms, algorithmic optimization.

What is the Number Field Sieve (NFS) mentioned in the document?

The Number Field Sieve (NFS) is the best-known classical algorithm for factoring large integers. This research seeks to improve the efficiency of the NFS algorithm using quantum computing techniques.

What is quantum annealing and how is it used in this research?

Quantum annealing is a quantum computing technique that's explored for integer factorization, particularly using D-Wave systems. The document discusses formulating the factorization problem as a QUBO (Quadratic Unconstrained Binary Optimization) and mapping it onto the quantum annealer's architecture.

What are quantum SAT solvers and how are they utilized in this context?

Quantum SAT solvers are another quantum computing approach investigated to speed up the Number Field Sieve (NFS). The research involves constructing SAT circuits related to integer factorization to leverage the potential speedup offered by these solvers.