2
$\begingroup$

Nobody seems to define the term anywhere. It's in the abstract of "Factoring integers with sublinear resources on a superconducting quantum processor" by Bao Yan, Ziqi Tan, Shijie Wei et alia, 2022.

Shor's algorithm has seriously challenged information security based on public key cryptosystems. However, to break the widely used RSA-2048 scheme, one needs millions of physical qubits, which is far beyond current technical capabilities. Here, we report a universal quantum algorithm for integer factorization by combining the classical lattice reduction with a quantum approximate optimization algorithm (QAOA).

$\endgroup$
0

2 Answers 2

1
$\begingroup$

"Nobody seems to define the term anywhere."

The term "universal quantum algorithm" is not commonly used. In the case of factoring numbers it could mean one of two things:

  1. Some algorithms for factoring numbers do not exploit "universal quantum computers" meaning that they could work on simpler quantum annealers like the D-Wave machine which cannot do universal quantum computation. These would not be "universal" quantum algorithms, and ones that do require universal quantum computers could (although it wouldn't be a very common way to say it) be called "universal".

  2. Some algorithms for factoring numbers cater only to specific types of numbers (e.g. semiprime numbers, or numbers of the form $(p-1)(q-1)$ for primes $p$ and $q$). These include:

  • Trial division
  • Wheel factorization
  • Pollard's rho algorithm
  • Algebraic-group factorization algorithms
  • Fermat's factorization method
  • Euler's factorization method
  • Special number field sieve

In the paper that you mentioned, the algorithm can run on a non-universal D-Wave machine (even though they used QAOA on a circuit-based machine to solve the QUBO part of their algorithm, instead of just running it on a D-Wave machine), they more likely to mean the second option above. They mean that their algorithm will work for the factorization of any integer.

I recently wrote a much longer explanation of that paper here, in the answer to Quantum Computing Used to Break RSA by "fixing" Schnorr's Recent Factorization Claim?.

$\endgroup$
2
$\begingroup$

I am not very sure, but it's not a technical term. It just means an algorithm that works in every case, more like a generalised algorithm. So what I think that means is that This algorithm will surely factor every integer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.