PaperlayerView exact revision on arXiv

Source-linked AI summary

Massively parallel quantum computer simulator, eleven years later

Hans De Raedt, Fengping Jin, Dennis Willsch, Madita Nocon, Naoki Yoshioka, Nobuyasu Ito, Shengjun Yuan, Kristel Michielsen

arXiv:1805.04708v2quant-phphysics.comp-ph

TL;DR

Classically simulating universal quantum computers is challenging because memory needs grow exponentially with qubit count and distributed computation adds communication overhead. The paper revises JUQCS for parallel simulation and supercomputer benchmarking, reporting strong scaling with compute nodes that outpaces the characteristic exponential growth in simulation time.

  • Problem

    Classical simulation requires exponentially increasing memory as qubits are added, and distributing computation introduces inter-node communication overhead.

    Source: §1 · pp. 1–2

  • Method

    The paper revises JUQCS with parallelization that minimizes inter-node data transfers to simulate gate-based quantum circuits.

    Source: §1 · pp. 1–2

  • Results

    JUQCS scales very well with compute nodes, beating the exponential growth in simulation time characteristic of universal-quantum-computer simulation.

    Source: §1 · p. 3

  • Takeaways & Limitations

    JUQCS can also serve as a benchmark tool for supercomputers through weak-scaling tests using quantum algorithms.

    Source: §1 · p. 3

    The portable code is not machine-specifically optimized to use accelerator hardware such as that in Sunway TaihuLight.

    Source: §1 · p. 3

Abstract

from arXiv · show

A revised version of the massively parallel simulator of a universal quantum computer, described in this journal eleven years ago, is used to benchmark various gate-based quantum algorithms on some of the most powerful supercomputers that exist today. Adaptive encoding of the wave function reduces the memory requirement by a factor of eight, making it possible to simulate universal quantum computers with up to 48 qubits on the Sunway TaihuLight and on the K computer. The simulator exhibits close-to-ideal weak-scaling behavior on the Sunway TaihuLight,on the K computer, on an IBM Blue Gene/Q, and on Intel Xeon based clusters, implying that the combination of parallelization and hardware can track the exponential scaling due to the increasing number of qubits. Results of executing simple quantum circuits and Shor's factorization algorithm on quantum computers containing up to 48 qubits are presented.

1. Introduction

The paper revises JUQCS to simulate gate-based quantum computers and benchmark supercomputers, addressing the exponential memory demands and communication overhead of classical simulation. Its adaptive version reduces memory needs, while the simulator scales well across compute nodes.

1. Introduction

  • Each added qubit doubles classical memory needs; a 45-qubit wave function requires slightly more than half a petabyte.The paper cites limited availability of computers with enough memory, processors, and network capacity for such simulations.Source: §1 · pp. 1–2
  • The benchmarks cover systems including the IBM Blue Gene/Q, K computer, Sunway TaihuLight, JURECA, and JUWELS.The paper also introduces an OpenQASM translator and operations for implementing error-correction schemes.Source: Table 1 · p. 2, §1 · p. 2
  • Adaptive coding reduces memory requirements eightfold, enabling simulations of up to 48 qubits with somewhat reduced numerical precision.The reduced precision is about three digits and was found sufficient for circuits tested so far.Source: §1 · p. 2
  • JUQCS minimizes inter-node data transfers to reduce communication overhead in distributed-memory simulations.The simulator supports OpenMP, MPI, or both, depending on the hardware.Source: §1 · p. 2
  • The auxiliary-field approach trades memory for CPU time and is most useful when few output amplitudes are needed and the circuit has relatively few two-qubit gates.Its usefulness is limited for Shor’s algorithm because the relevant basis states are not known in advance.Source: §1 · p. 2
  • JUQCS prioritizes portability over machine-specific optimization, leaving use of accelerator hardware such as Sunway TaihuLight’s to future work.On a 16GB notebook, JUQCS–A and JUQCS–E can simulate 32 and 29 qubits, respectively.Source: §1 · p. 3
  • JUQCS scales very well with compute nodes, beating the exponential growth in simulation time and serving as a supercomputer benchmark tool.The paper reports weak-scaling plots from quantum-algorithm runs on supercomputers.Source: §1 · p. 3

2. Basic operation

A gate-based quantum computer is represented by a normalized vector of complex amplitudes, updated through sparse matrix-vector operations. The simulator applies these updates to selected amplitude groups, with gate operations exposing parallel work.

2. Basic operation

  • A quantum computer’s internal state is a normalized vector of 2^N complex amplitudes, where N is the number of qubits.The literature convention described here numbers qubits from 0 to N−1, with qubit 0 at the rightmost bit.Source: §2 · p. 3
  • Universal gate-based algorithms apply unitary operations to the state vector, using single-qubit operations and CNOT gates as the elementary operations.The vector stores amplitudes for all basis states.Source: §2 · p. 3
  • A single-qubit gate updates pairs of amplitudes, and the Hadamard operation can be performed in place with only O(1) additional memory.Its sparse matrix-vector multiplication decomposes into 2^(N−1) operations on vectors of length two.Source: §2 · p. 3
  • Amplitude-pair updates expose substantial intrinsic parallelism, while two- and three-qubit gates update groups of four and eight amplitudes, respectively.CNOT and Toffoli gates exchange only two amplitudes within their respective groups.Source: §2 · p. 4
  • The final state supports measurement-probability calculations and event generation for individual qubits.The probabilities are computed by summing squared amplitudes for outcomes 0 and 1.Source: §2 · p. 4

3. Parallelization techniques

The section describes OpenMP and MPI strategies for distributing gate updates across cores and compute nodes. MPI avoids communication for local-qubit operations, but nonlocal operations require data movement between nodes.

3.1. OpenMP

  • OpenMP distributes amplitude-group loops across cores, using a simple cache-conscious loop order and a universal test to choose which loops to parallelize.Experiments found the test was not optimal across N and hardware, but the computation-time reduction from a better choice was marginal.Source: §3.1 · p. 4

3.2. MPI

  • High-order index bits assign amplitude blocks to compute nodes, with each node storing the amplitudes indexed by the remaining bits.For N qubits, the scheme uses N_h high-order bits to identify 2^N_h nodes and leaves N_l = N − N_h bits for the amplitudes on each node.Source: §3.2 · p. 4
  • Operations on nonlocal qubits require inter-node data exchange; JUQCS swaps nonlocal and local qubits and tracks the swaps through index permutations.For a Hadamard gate, this can transfer half of all amplitudes, and the swaps are time-consuming when N is large.Source: §3.2 · p. 4

3.1. OpenMP

  • Two- and three-qubit gates extend the loop scheme, but JUQCS does not exploit the special structure of CNOT and Toffoli gates in its MPI communication scheme.The two-qubit implementation uses three loops, and the scheme extends to three-qubit gates.Source: §3.2 · p. 4, §3.1 · p. 4

4. Trading memory for CPU time

The section addresses the memory needed to store an exponentially growing quantum state by trading additional computation time for lower memory use. It presents adaptive byte encoding and an auxiliary-variable method, whose memory benefit depends on the requested output.

4. Trading memory for CPU time

  • Reducing the memory needed to store the 2^N amplitudes comes at the price of increased computation time.The section presents two methods for making this trade-off.Source: §4 · p. 5

4.1. Double precision versus byte encoding

  • Adaptive encoding stores each amplitude in two bytes, reducing state memory by a factor of eight while adding gate-dependent encoding and decoding work.The added CPU time ranges from very little for X or CNOT gates to a factor of 3–4 for Hadamard or +X gates.Source: §4.1 · p. 5

4.2. Auxiliary variable method

  • For M requested amplitudes, the auxiliary-variable method has worst-case time O(NM2^P) and memory O(N + M), but its memory advantage disappears when the full state is required.It requires a product-state input; when M ≪ 2^N, its memory use can be much lower than O(2^N).Source: §4.2 · pp. 5–6
  • Controlled-phase shifts and CNOT gates can be rewritten using two-valued auxiliary variables, yielding independently computable single-qubit-operation terms.The method introduces one variable for each controlled-phase shift, including those arising from rewriting CNOT gates.Source: §4.2 · p. 6

5. Validation and benchmarking

Known-output circuits validate JUQCS while benchmarking its scaling; doubling machine size per added qubit lets it beat exponential work growth in Hadamard and CNOT tests. The section also reports an adder test and examines qubit limits for Shor’s algorithm.

5. Validation and benchmarking

  • Validation uses circuits with known exact input-output relations to check JUQCS and illustrate its supercomputer scaling and performance.Source: §5 · p. 6

5.1. Uniform superposition

  • For uniform-superposition tests, JUQCS–A matched JUQCS–E’s exact results using eightfold less memory, reaching 48 qubits on Sunway TaihuLight and the K computer.The table reports results for the two simulator versions across several supercomputers.Source: Table 2 · p. 7
  • Doubling machine size per added qubit lets JUQCS beat exponential work growth in Hadamard and CNOT circuits.The weak-scaling figures show elapsed time per gate operation across increasing qubit counts.Source: §5.1 · p. 7, Figure 1 · p. 7, §5.2 · p. 7

5.2. Sequence of CNOT gates

  • CNOT and X gates have low arithmetic intensity and are memory-bandwidth-limited; 2-byte encoding adds almost no CNOT time but 3–4x for Hadamard gates.The authors suggest combining gates to increase arithmetic intensity but did not implement that specialized strategy.Source: §5.2 · pp. 7–8

5.3. Adder circuit

  • For a two-19-bit-integer adder on 8192 cores, JUQCS–A took 1446 s versus JUQCS–E’s 388 s; A was close but not always numerically exact.The selected inputs make the expected all-one qubit outputs easy to verify.Source: §5.3 · p. 8

5.4. Shor’s algorithm on a 48 qubit quantum computer

  • For 45- or 46-qubit computers, the stated Shor register constraints make 32765 the largest integer composed of two primes that can be factored.The f-register size is F = floor((N + 1)/3).Source: §5.4 · p. 9

H QFT x

The section reports Shor-algorithm simulations up to 48 qubits, alongside comparisons of JUQCS–A results with exact results at 30 and 45 qubits.

H QFT x

  • Figure 5 is a schematic diagram of Shor’s algorithm.Source: Figure 5 · p. 9
  • For G = 1007 and y = 529, JUQCS–A results using 30 qubits agreed very well with exact results.The simulation ran on a Lenovo W520 notebook.Source: H QFT x · p. 9
  • At 45 qubits, JUQCS–A agreed very well with exact expectation values; the authors conjecture comparable accuracy of about 3 digits on single-qubit expectations exceeds present and future gate hardware.The run used G = 32399 and y = 4295 on JUQUEEN.Source: H QFT x · p. 9
  • At 48 qubits, Shor simulations returned periods that yielded the factorizations 64507 = 251 × 257 and 65531 = 19 × 3449.Runs took about 347 minutes on Sunway TaihuLight and 299–300 minutes on the K computer.Source: H QFT x · p. 9

6. Conclusion

JUQCS showed close-to-linear weak scaling across four computer platforms, while adaptive coding reduced memory use eightfold without significant accuracy impact in reported benchmarks. A second memory-reduction technique has limited practical use without a way to select basis states, and accelerator optimization remains future work.

6. Conclusion

  • Close-to-linear weak scaling was observed across Sunway TaihuLight, the K computer, IBM Blue Gene/Q, and Intel Xeon clusters.The paper says software, many cores, and fast communication together beat the exponential increase in memory and CPU time characteristic of digital quantum simulation.Source: §6 · p. 9
  • Adaptive coding uses 2-byte rather than 16-byte numbers, reducing memory by a factor of eight without significant accuracy impact across the reported benchmarks.The benchmarks include Shor’s algorithm, adders, quantum Fourier transforms, Hadamard, and CNOT operations; the adaptive version can simulate 32 qubits on a 16 GB notebook.Source: §6 · p. 9
  • The auxiliary-variable technique has worst-case runtime O(NM2P) and memory O(N + M), but is of limited practical use unless M basis states of interest can be chosen.Source: §6 · p. 9
  • Efficient use of GPUs or other accelerators remains future work; Sunway TaihuLight requires machine-specific programming to use its accelerator hardware.JUQCS inputs can be tailored to burden communication, memory, processing, or combinations of these resources.Source: §6 · p. 10

Appendix A. Instruction set

  • Appendix A specifies implemented gate operations; the paper says JUQCS would become accessible through a Jülich cloud service in 2019 and that Dockerized executables were available on request.Source: Appendix A · p. 10

I gate

The I gate performs an identity operation on a selected qubit and is implemented as a no-op for compatibility.

I gate

  • The I gate performs an identity operation on qubit n.Source: I gate · p. 10
  • The argument n ranges from 0 through N − 1, where N is the number of qubits.Source: I gate · p. 10
  • In JUQCS, the I gate is implemented as a no-op and is provided only for compatibility with some other assembler-like language.Source: I gate · p. 10

H gate

The H gate performs a Hadamard operation on a selected qubit, with n indexing the qubits from 0 to N − 1.

H gate

X gate

The X gate performs a bit flip on qubit n, where n ranges from 0 to N −1 for an N-qubit computer.

X gate

  • The X gate flips qubit n; n must be in the range 0,...,N −1, where N is the number of qubits.Source: X gate · p. 10

Y gate

This section lists JUQCS gate instructions, measurements, and configuration commands, including their supported operations and arguments.

Y gate; Z gate

  • The Y gate performs bit and phase flips, while the Z gate performs a phase flip on qubit n.For both gates, n ranges from 0 to N −1.Source: Y gate · p. 10, Z gate · p. 10

S gate; T gate; U1 gate; U2 gate; U3 gate

+X gate; -X gate; +Y gate; -Y gate

R(k) gate; CNOT gate; U(k) gate; Toffoli gate

  • R(k) and its inverse change qubit n’s phase by ±2π/2^k; CNOT conditionally flips its target, and controlled-phase and Toffoli gates apply their specified conditional operations.For controlled-phase, the phase shift is 2π/2^k when the control is 1; Toffoli flips the target when both controls are 1.Source: R(k) gate · p. 12, CNOT gate · p. 12, U(k) gate · p. 12

BEGIN MEASUREMENT; GENERATE EVENTS

  • BEGIN MEASUREMENT reports qubit expectation values without changing the state; GENERATE EVENTS samples basis states from the current state’s probabilities and then destroys that state.The event count must be positive; M instead performs a projective measurement on qubit n.Source: BEGIN MEASUREMENT · p. 13, GENERATE EVENTS · p. 13

QUBITS; BIT ASSIGNMENT

  • QUBITS sets N, while BIT ASSIGNMENT permutes qubit numbering and may reduce MPI communication without changing the circuit.N must be greater than 1 and less than 64, with the actual limit set by available memory; BIT ASSIGNMENT requires a permutation of 0,...,N −1.Source: QUBITS · p. 13, BIT ASSIGNMENT · p. 13

SHORBOX

The section describes commands for initializing Shor’s algorithm registers and for inserting probabilistic gate errors.

SHORBOX

  • SHORBOX initializes Shor’s x-register in uniform superposition and the f-register in y^x mod G, with G to factor and y coprime to G.Applying the quantum Fourier transform to the x-register allows determination of the function’s period, from which factors of G may be calculated.Source: SHORBOX · p. 14
  • CLEAR and SET project a qubit to |0⟩ and |1⟩, respectively, and fail if the resulting state has zero amplitude.Source: SHORBOX · p. 14

DEPOLARIZING CHANNEL

  • DEPOLARIZING CHANNEL inserts X, Y, or Z gates after each gate operation with specified probabilities.Each probability lies between 0 and 1, and their sum must not exceed 1.Source: DEPOLARIZING CHANNEL · p. 14

Appendix B. Illustrative example

The example walks through JUQCS instructions for a three-qubit logical error-correction circuit and reports how it responds to one- and two-qubit errors.

Appendix B. Illustrative example

  • The circuit encodes a logical qubit in qubits 0–2, uses qubits 3 and 4 for error correction, and includes measurements and qubit resets.The instructions prepare the input state, encode it, introduce a single-qubit error, detect and correct errors, and generate 8192 sampled output events.Source: Appendix B · pp. 14–15, Figure B.6 · p. 15
  • The example’s code detects and corrects a single-qubit error, but fails to correct two-qubit errors.The reported outputs compare no injected error, an error on qubit 0, and errors on qubits 0 and 1.Source: Appendix B · p. 15
Loading 1805.04708v2…