Quantum computers have the potential to perform computational tasks beyond the reach of classical machines. A prominent example is Shor's algorithm for integer factorization and discrete logarithms, which is of both fundamental importance and practical relevance to cryptography. However, due to the high overhead of quantum error correction, optimized resource estimates for cryptographically relevant instances of Shor's algorithm require millions of physical qubits. Here, by leveraging advances in high-rate quantum error-correcting codes, efficient logical instruction sets, and circuit design, we show that Shor's algorithm can be executed at cryptographically relevant scales with as few as 10,000 reconfigurable atomic qubits. Increasing the number of physical qubits improves time efficiency by enabling greater parallelism; under plausible assumptions, the runtime for discrete logarithms on the P-256 elliptic curve could be just a few days for a system with 26,000 physical qubits, while the runtime for factoring RSA-2048 integers is one to two orders of magnitude longer. Recent neutral-atom experiments have demonstrated universal fault-tolerant operations below the error-correction threshold, computation on arrays of hundreds of qubits, and trapping arrays with more than 6,000 highly coherent qubits. Although substantial engineering challenges remain, our theoretical analysis indicates that an appropriately designed neutral-atom architecture could support quantum computation at cryptographically relevant scales. More broadly, these results highlight the capability of neutral atoms for fault-tolerant quantum computing with wide-ranging scientific and technological applications.
Quantum circuits consist of a cascade of quantum gates. In a physical design-unaware quantum logic circuit, a gate is assumed to operate on an arbitrary set of quantum bits (qubits), without considering the physical location of the qubits. However, in reality, physical qubits have to be placed on a grid. Each node of the grid represents a qubit. The grid implements the architecture of the quantum computer. A physical constraint often imposed is that quantum gates can only operate on adjacent qubits on the grid. Hence, a communication channel needs to be built if the qubits in the logical circuit are not adjacent. In this paper, we introduce a tool called the physical design-aware fault-tolerant quantum circuit synthesis (PAQCS). It contains two algorithms: one for physical qubit placement and another for routing of communications. With the help of these two algorithms, the overhead of converting a logical to a physical circuit is reduced by 30.1%, on an average, relative to previous work. The optimization algorithms in PAQCS are evaluated on circuits implemented using quantum operations supported by two different quantum physical machine descriptions and three quantum error-correcting codes. They reduce the number of primitive operations by 11.5%-68.6%, and the number of execution cycles by 16.9%-59.4%.
Obtaining a quantum advantage in practical applications over classical machines requires a fault-tolerant model of computation. However, the resource overhead of developing a fault-tolerant quantum computer (FTQC) architecture is quite high. Current state-of-the-art architecture designs promise constant-time access to logical qubits at the expense of a high qubit overhead, or qubit-dense layouts at the expense of increased latency in the execution of a quantum workload. In this paper, we propose (a) an architecture design that balances the tradeoff of execution time of workloads with the density of logical qubits by placing the surface code patches around the ancilla region, giving almost equal access of the ancilla region to all the data qubits, (b) design a novel algorithm to leverage the
T-gate characteristics of the user workload to suggest the optimal placement strategy in the floorplan of our architecture, (c) a workload-selective fast-
Y optimization knob that accelerates
Y-basis measurements only for qubits whose
Y-gate demand justifies the additional tile cost, and (d) explore the scope of executing multiple programs concurrently, which enhances the reconfigurability of our proposed design. Through numerical evaluation, we observe that the proposed architecture design maintains the cycles per instruction time close to optimal while using up to
∼21% fewer data tiles, and up to
∼90% efficiency under a 10-way concurrency.