PaperlayerView exact revision on arXiv

Source-linked AI summary

Advanced Simulation of Quantum Computations

Alwin Zulehner, Robert Wille

arXiv:1707.00865v3quant-phcs.ET

TL;DR

Quantum simulation on conventional machines is difficult because state vectors and operation matrices grow exponentially, while existing array- and graph-based methods do not exploit all available redundancies. The paper introduces a more natural decision-diagram representation for quantum states and operations, yielding a graph-based simulator that handles more qubits with substantially lower runtime and memory.

  • Problem

    Quantum simulation requires exponentially large state vectors and operation matrices, while existing simulators do not fully exploit redundancies in these representations.

  • Method

    The paper develops a graph-based simulator using a decision-diagram decomposition more natural for quantum states and operations, thereby exploiting additional redundancies.

  • Results

    The proposed approach outperforms array-based and graph-based state-of-the-art simulators, simulating more qubits with substantially less runtime and up to 260 MB of memory.

  • Takeaways & Limitations

    Quantum computations can be simulated on a single core of a regular desktop machine rather than requiring massive hardware power or supercomputers.

Abstract

from arXiv · show

Quantum computation is a promising emerging technology which, compared to conventional computation, allows for substantial speed-ups e.g. for integer factorization or database search. However, since physical realizations of quantum computers are in their infancy, a significant amount of research in this domain still relies on simulations of quantum computations on conventional machines. This causes a significant complexity which current state-of-the-art simulators try to tackle with a rather straight forward array-based representation and by applying massive hardware power. There also exist solutions based on decision diagrams (i.e. graph-based approaches) that try to tackle the exponential complexity by exploiting redundancies in quantum states and operations. However, these existing approaches do not fully exploit redundancies that are actually present. In this work, we revisit the basics of quantum computation, investigate how corresponding quantum states and quantum operations can be represented even more compactly, and, eventually, simulated in a more efficient fashion. This leads to a new graph-based simulation approach which outperforms state-of-the-art simulators (array-based as well as graph-based). Experimental evaluations show that the proposed solution is capable of simulating quantum computations for more qubits than before, and in significantly less run-time (several magnitudes faster compared to previously proposed simulators). An implementation of the proposed simulator is publicly available online at http://iic.jku.at/eda/research/quantum_simulation.

I. INTRODUCTION

Quantum computation offers major theoretical speedups, but its simulation remains necessary while physical quantum computers are emerging. The paper proposes a more compact graph-based representation to exploit redundancies and accelerate simulation.

  • Quantum algorithms for integer factorization and database search can provide significant, sometimes exponential, speedups over conventional computation.
  • Simulation on conventional machines is needed for developing and verifying quantum computers, despite the speedups of the underlying algorithms.
  • Array-based simulators represent exponentially large state vectors and operation matrices directly, then rely on parallelism and massive hardware power.
  • Existing decision-diagram simulators exploit redundancies, but do not fully capture the redundancies present in quantum states and operations.
  • The proposed decision diagram uses a decomposition more natural for quantum matrices and vectors, enabling more compact representations and dedicated manipulation algorithms.
  • The resulting approach simulates Shor’s Algorithm and Grover’s Search for more qubits, completing many simulations in hours, minutes, or seconds instead of several days.

a valid state, since

Quantum systems use complex amplitudes and reversible unitary operations, while quantum circuits describe sequences of operations applied to qubits. Controlled operations extend single-qubit gates by conditioning them on other qubits.

  • Measuring a two-qubit state can yield basis states such as |00⟩ or |11⟩, illustrating measurement outcomes for a superposed system.
  • Quantum operations, except measurement, are reversible and represented by unitary matrices whose size depends on the involved qubits.
  • The X, H, and Z gates respectively complement a qubit, create superposition, and change its phase.
  • A controlled inversion applies X to a target qubit when the control is |1⟩ and applies the identity when the control is |0⟩.
  • The matrix for a gate controlled by multiple qubits grows exponentially with the number of control qubits.
  • A quantum circuit orders operations from left to right on vertically aligned qubit lines, with boxes indicating applied operations.
  • In the example circuit, a Hadamard gate creates superposition on q0, CNOT couples q0 and q1, and measuring q0 collapses its superposition.

III. CONDUCTING SIMULATION

Quantum-circuit simulation successively applies operation matrices to state vectors, but both representations grow exponentially with the number of qubits. Entanglement prevents reducing the computation to independent local operations.

  • Simulators execute a sequence of quantum operations by multiplying each operation matrix with the corresponding intermediate state vector.
  • Operations acting on fewer than n qubits are expanded to 2^n × 2^n matrices using identity matrices and Kronecker products.
  • A. Exponential Growth: The state vectors and operation matrices both require exponential space as the number of qubits increases.
  • A. Exponential Growth: Applying gates only to affected qubits cannot generally avoid exponential growth because entanglement links the states of multiple qubits.
  • A. Exponential Growth: Measurement of an entangled state can collapse one qubit while determining the state of another dependent qubit.

the basis state |0⟩or |1⟩with a probability

Quantum simulation remains difficult because entanglement can require the complete exponential state vector, while existing array- and graph-based simulators face practical size and runtime limits.

  • Entanglement can make local reasoning insufficient, requiring the complete exponential state vector for simulation.
  • Existing array-based simulators use straightforward state and operation representations and are consequently limited in scale.
  • LIQUi|⟩ simulates approximately 30 qubits on a desktop with 32 GB RAM, with runtimes up to several days.
  • qHiPSTER simulates no more than 40 qubits using 1000 compute nodes and 32 TB of distributed RAM.
  • Other reported limits include 36 qubits for the Quantum Emulator, 34 fully entangled qubits for QX, and approximately 30 qubits for ProjectQ on desktop hardware.
  • QuIDDPro exploits redundancies and simulates Grover’s algorithm faster than array-based solutions, but its node count is non-scalable for Quantum Fourier Transformation and Shor’s Algorithms.

C. General Idea

The proposed state-vector representation decomposes vectors into reusable sub-vectors and uses weighted, reduced, normalized decision diagrams to exploit structural and factor redundancies.

  • C. General Idea: The approach uses a decomposition scheme natural to quantum states and operations, yielding compact representations and efficient manipulation algorithms.Some operations can reduce to rearranging pointers in the decision diagram.
  • Sharing redundancies: Equivalent sub-vectors can be shared, producing a more compact graph representation than the original vector.Decision-diagram techniques exploit repeated sub-functions or sub-vectors as shared nodes.
  • State-vector decomposition: A state vector is recursively decomposed by qubit partitions into sub-vectors represented by decision-diagram nodes.The left and right successors correspond to amplitudes whose selected qubit is |0⟩ and |1⟩, respectively.
  • Weighted edges: Common amplitude factors are stored as edge weights, so amplitudes are obtained by multiplying weights along root-to-terminal paths.This allows structurally equivalent sub-trees that differ only by common factors to be merged.
  • Normalization: Normalization divides edge weights by a selected nonzero factor and propagates the common factor upward; zero-left-edge cases propagate the right weight.
  • Formal representation: The resulting state-vector diagram is a reduced, normalized directed acyclic graph with one terminal labeled 1 and complex weights on edges.

B. Representation of Matrices

Quantum operations are represented by extending the state-vector decomposition to two dimensions, recursively partitioning unitary matrices into sub-matrices and sharing redundant structure.

  • Matrix decomposition: The state-vector decomposition is extended to 2^n × 2^n unitary matrices for representing quantum operations.
  • Matrix decomposition: Each matrix partition separates mappings according to whether the most significant qubit is |0⟩ or |1⟩ in the source and target basis states.
  • Notation: Zero matrices can be represented with zero stubs, and unit edge weights can be omitted from the graphical notation.
  • Example: For U = H ⊗ I2, a path through the diagram identifies a basis-state mapping and its matrix value by multiplying the path factors.
  • Formal representation: The matrix decision diagram assigns complex weights to edges, with each matrix entry determined by multiplying weights along a root-to-terminal path.
  • Reduction and normalization: Reduction removes nodes whose four outgoing branches represent identical sub-matrices, while normalization divides edge weights by the first nonzero weight and propagates the common factor upward.

V. CONDUCTING QUANTUM SIMULATIONS

The proposed representations support the operations needed for quantum simulation, including Kronecker products, matrix–vector multiplication, and measurement, through decomposition-aware recursive procedures.

  • The simulator must provide methods for Kronecker products, multiplying vectors with matrices, and measuring quantum systems.
  • Because the decomposition scheme matches the structure of vectors and matrices, these operations can be implemented efficiently.

A. Kronecker Product

The proposed decision diagram makes Kronecker products cheap by replacing one matrix’s terminal with the other’s root. Its recursive matrix-vector multiplication decomposes into cached sub-products and sub-sums without changing the diagram structure.

  • A. Kronecker Product: Kronecker products have complexity O(|v|) in the proposed decision diagram.The operation replaces A’s terminal with B’s root and adjusts edge weights rather than expanding matrix entries.
  • A. Kronecker Product: The proposed Kronecker-product construction is cheaper than array-based expansion because each A entry need not be separately multiplied by B.In QuIDDs, terminal values of both matrices must instead be multiplied.
  • A. Kronecker Product: Matrix-vector multiplication recursively computes four sub-products, combines them into intermediate vectors, and then adds those vectors.The sub-products are U00·ψ0, U01·ψ1, U10·ψ0, and U11·ψ1.
  • A. Kronecker Product: Recursive decompositions preserve the original decision-diagram structure, keeping complexity bounded by its node count.Caching can additionally reuse repeated sub-products and sub-sums.

C. Measurement

Measurement is performed directly on the decision diagram by computing weighted probabilities for the root node’s sub-vectors, sampling an outcome, and modifying edges to realize collapse and renormalization.

  • C. Measurement: Measurement probabilities for q0 are sums of squared amplitude magnitudes in the corresponding sub-vectors.The left and right root successors represent the q0=|0⟩ and q0=|1⟩ sub-vectors.
  • C. Measurement: The example state collapses q0 to |0⟩ or |1⟩ with probabilities 0.25 and 0.75, respectively.These probabilities determine the sampled measurement outcome.
  • C. Measurement: Decision-diagram node probabilities are computed recursively by summing successor probabilities weighted by squared edge magnitudes.The sub-vector probabilities are recursively determined before being combined at the current node.
  • C. Measurement: After sampling, collapse is represented by redirecting the excluded root edge to the terminal with weight zero and renormalizing the remaining state.Renormalization is performed by modifying the root-edge weight.
  • C. Measurement: All qubits can be measured sequentially, with each next measured qubit represented by the root of the relevant sub-vector.The procedure is repeated for q0 through qn−1.

VI. DISCUSSION

The discussion compares the proposed graph-based approach with array-based and other graph-based simulators by separating representation complexity from operation complexity.

  • VI. DISCUSSION: The paper analyzes the proposed approach against array-based and graph-based solutions in terms of representation and operation complexity.This comparison is intended to explain why the approach can outperform alternatives in many cases.

A. Representation of Vectors and Matrices

Graph-based representations can compress quantum states and operations by exploiting redundancies, while edge weights and normalization expose more sharing than prior graph-based methods. Their operations are correspondingly efficient in many cases, though the representation has an exponential worst case.

  • A. Representation of Vectors and Matrices: Graph-based representations are often more compact than arrays, and edge weights plus normalization exploit more redundancies than previous graph-based solutions.Array-based methods always store 2^n-dimensional vectors and 2^n × 2^n-dimensional matrices.
  • A. Representation of Vectors and Matrices: 2^n nodes and 2^(n+1)−1 complex edge weights form the proposed representation’s worst case.This is approximately twice as many complex numbers as array-based solutions and QuIDDs for state vectors.
  • A. Representation of Vectors and Matrices: Elementary operations with one target qubit and arbitrary controls require a number of matrix nodes linear in the qubit count.The matrix representation is otherwise analogous to the state-vector memory discussion.
  • A. Representation of Vectors and Matrices: The proposed Kronecker product exchanges diagram nodes with complexity O(|v|), while matrix-vector multiplication has complexity O(n · |v|).The latter bound uses matrices whose node count grows linearly with n.
  • A. Representation of Vectors and Matrices: Measuring all qubits has complexity O(|v| + n), because each node is traversed once and each qubit is then processed in O(1).This operation-level efficiency contributes to the broader advantage of graph-based manipulation in many cases.
  • A. Representation of Vectors and Matrices: The proposed simulator can outperform array-based methods and QuIDDPro by exploiting more redundancies, despite decision-diagram overhead.The paper states that empirical evaluation confirms significant performance improvement compared with QuIDDPro.

VII. EXPERIMENTAL RESULTS

The evaluation compares the proposed simulator with array-based and graph-based state-of-the-art implementations across entanglement, QFT, Grover’s Algorithm, and Shor’s Algorithm. The proposed approach scales better, uses less runtime and memory, and handles more qubits on ordinary hardware.

  • Evaluation setup: The evaluation compares the proposed C++ simulator with LIQu|⟩, QX, ProjectQ, and QuIDDPro using established quantum-algorithm benchmarks.The benchmarks include entangled-state generation, QFT, Grover’s Algorithm, and Shor’s Algorithm.
  • Evaluation scope: The comparison accounts for simulator restrictions, including LIQu|⟩’s publicly available limit of at most 23 qubits and QX’s memory and language limitations.Unavailable cases are marked as not applicable, and QuIDDProLite is used where its circuit-only scope permits.
  • Scalability: The proposed simulator shows linear behavior for entangled-state generation and QFT, whereas several array-based simulators show exponential behavior.QuIDDPro remains linear for entanglement but becomes exponential for QFT because it cannot exploit the relevant sub-vector redundancies.
  • Algorithmic benchmarks: Shor’s Algorithm with 37 qubits requires slightly more than 20 000 nodes and completes in less than a minute with the proposed approach.LIQu|⟩ handles at most 31 qubits in more than 30 days under the cited comparison.
  • Algorithmic benchmarks: The proposed approach simulates Grover’s and Shor’s Algorithms more efficiently and for more qubits than both array-based and graph-based alternatives.QuIDDPro incurs substantial runtime for Grover’s Algorithm and has limitations comparable to array-based solutions for Shor’s Algorithm.
  • Overall results: The simulator outperforms the state of the art in runtime and memory, requiring at most 260 MB while running on a single core of a regular desktop machine.These results are achieved without massive hardware power or supercomputers.
Loading 1707.00865v3…