# Factoring 2048-bit integer with quantum computer?

In this paper, there is a statement in the abstract:

Our construction uses $$3n + 0.002n \log(n)$$ logical qubits, $$0.3n^3 + 0.0005n ^3\log(n)$$ Toffolis, and $$500n^2 +n^2 \log(n)$$ measurement depth to factor n-bit RSA integers.

The title of the paper states that 20.000.000 qubits are used to crack RSA-2048 where this presentation -also refers that paper- includes table in pg.22 that maps RSA-2048 to 6189 qubits.

My question is: Which one is the quantity that should be considered for following development in quantum computers? In other words, what is the necessary number of qubits for quantum computers to crack RSA-2048 according to this paper? 6189 or 20.000.000?

Also, definitions of logical qubit, noisy qubit, measurement depth and Toffoli can be very useful for understanding this concept.

• Main question is: which one will factor 2048-bit integer according to this work? 6189-qubit or 20.000.000-qubit quantum computer? Jan 19 at 10:39
• Section 2.4 of the paper talks about `switch from the usual representation of integers to the coset representation of modular integers. and see en.wikipedia.org/wiki/… Jan 19 at 11:24
• I am trying to understand general concept by just focusing on number of qubits. What represents 6189 and 20.000.000? Can we say 20.000.000 noisy qubit corresponds 6189 abstract qubits? And which one corresponds the number that declared by e.g. IBM as number of qubits of quantum computer. Jan 19 at 12:03
• What is the difference between a physical and a logical qubit? Jan 19 at 14:12
• Understanding (theoretical) computing power of quantum computers Jan 19 at 14:58

A Toffoli gate is a basic sort of gate that enables very general quantum circuits to be built (analogous to how Shannon's theorem allows us to build general computational circuits from NAND gates). From an engineering perspective it is usually the most difficult basic gate to implement and so the number of Toffoli gates is another measure of the engineering challenge. On classical data a Toffoli gate sends three input bits $$(a,b,c)$$ to three output bits $$(a,b,c\oplus a\cdot b)$$.