PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning the quantum algorithm for state overlap

Lukasz Cincio, Yiğit Subaşı, Andrew T. Sornborger, Patrick J. Coles

arXiv:1803.04114v2quant-ph

TL;DR

Near-term quantum computers require shorter algorithms because decoherence and gate infidelity limit implementable depth and increase computational error. The paper uses machine learning to discover state-overlap algorithms under fixed resources and hardware constraints, finding constant-depth and hardware-specific alternatives to the Swap Test. These alternatives reduce circuit depth and, on IBM and Rigetti devices, computational error relative to the Swap Test.

  • Problem

    Decoherence, gate infidelity, limited connectivity, and differing native gate sets make low-error quantum algorithms difficult to implement on near-term hardware.

  • Method

    A machine-learning approach searches over quantum gate sequences and classical post-processing for fixed resources, using training data to discover small algorithms and hardware-specific implementations.

  • Results

    The BBA achieves constant circuit depth with linear classical post-processing, while hardware-specific algorithms reduce RMS error by 66% on IBM’s 5-qubit computer and 70% on Rigetti’s 19-qubit computer versus the Swap Test.

  • Takeaways & Limitations

    State overlap can be computed with more efficient circuits than the Swap Test, including a Bell-basis-based constant-depth algorithm for near-term quantum computers.

Abstract

from arXiv · show

Short-depth algorithms are crucial for reducing computational error on near-term quantum computers, for which decoherence and gate infidelity remain important issues. Here we present a machine-learning approach for discovering such algorithms. We apply our method to a ubiquitous primitive: computing the overlap ${\rm Tr}(ρσ)$ between two quantum states $ρ$ and $σ$. The standard algorithm for this task, known as the Swap Test, is used in many applications such as quantum support vector machines, and, when specialized to $ρ= σ$, quantifies the Renyi entanglement. Here, we find algorithms that have shorter depths than the Swap Test, including one that has a constant depth (independent of problem size). Furthermore, we apply our approach to the hardware-specific connectivity and gate sets used by Rigetti's and IBM's quantum computers and demonstrate that the shorter algorithms that we derive significantly reduce the error - compared to the Swap Test - on these computers.

I. INTRODUCTION

Near-term quantum computers motivate automated methods for reducing algorithm depth and implementation error. Applied to state overlap, the paper discovers shorter circuits than the Swap Test, including a constant-depth algorithm and hardware-specific variants.

  • Motivation: Decoherence, imperfect gate fidelity, limited connectivity, and differing gate sets constrain short-depth quantum algorithms on near-term hardware.These constraints motivate automated discovery and optimization for specific hardware resources.
  • Approach: Machine learning optimizes gate sequences and classical post-processing for fixed quantum resources, using training examples to discover algorithms that can generalize.The approach can target ideal hardware or hardware with non-ideal connectivity and gate sets.
  • Target task: State overlap computes Tr(ρσ), reduces to |⟨ψ|φ⟩|^2 for pure states, and gives purity Tr(ρ^2) when ρ = σ.The Swap Test supports applications including quantum supervised learning and Renyi order-2 entanglement quantification.
  • Hardware evaluation: 66% and 70% reductions in root-mean-square error were obtained on IBM’s 5-qubit and Rigetti’s 19-qubit computers, respectively, relative to the Swap Test.The paper also presents hardware-specific algorithms adapted to each computer’s connectivity and gate set.
  • Discovered algorithms: The Swap Test has linear circuit depth in qubit number, whereas the BBA has constant depth and linear classical post-processing complexity.The ABA retains linear depth but reduces the CNOT-decomposed gate count by a factor of ∼2.3.

II. MACHINE-LEARNING APPROACH

The method separates fixed quantum resources from an optimizable algorithm. It searches over gate sequences, continuous gate parameters, and simple classical post-processing to minimize task error.

  • Resources: Quantum resources include input ancilla and data qubits plus the locations of output measurements.For a single-qubit Swap Test, the resources are one ancilla, two data qubits, and measurement only on the ancilla.
  • Algorithm representation: The algorithm is parameterized by a discrete gate-sequence vector, continuous gate parameters, and a classical post-processing vector.Together these vectors define the algorithm for fixed resources.
  • Hardware dependence: The gate set depends on hardware connectivity and native gates, such as CNOTs for IBM and controlled-Z gates for Rigetti.One-qubit gates are treated as equally complex in this work, although the framework could model differing complexities.
  • Post-processing: Measurement probabilities are combined linearly with coefficients c_l ∈ {−1, 0, 1} to reveal the desired output.Computational-basis measurements suffice because basis changes can be incorporated into the gate sequence.

C. Optimization

The optimization defines a cost measuring discrepancy between desired and actual outputs, then searches fixed-depth algorithm spaces using training data. It identifies minimum gate counts where the cost is essentially zero.

  • The cost function quantifies the discrepancy between desired outputs and actual outputs on training data.
  • Training data is split evenly between optimization and performance testing, with coverage of possible inputs required.For state overlap, the estimated training-set size scales as 2^2nD.
  • For overlap, training examples pair quantum states ρ and σ with targets Tr(ρσ), and randomly sampled pure states suffice because pure-state algorithms also compute mixed-state overlap.
  • With Swap Test resources, the reported minimum gate counts are dmin = 8 for one-qubit states and dmin = 14 for n = 2.
  • For each fixed gate count d, the search minimizes cost and identifies an algorithm instance when cost falls below 10^-6.The minimum gate count dmin is the smallest d at which the cost can be minimized to essentially zero.
  • One optimization iteration randomly updates gate structure and post-processing, reoptimizes one-qubit parameters, then compares the resulting cost with the current best.

D. Details of the optimization techniques

The search combines discrete circuit and post-processing updates with continuous gate-parameter optimization, acceptance rules, and periodic circuit compression. It is computationally constrained by exponential training-data and search-space growth.

  • Discrete parameters encode circuit topology and post-processing, while continuous angles specify parameterized one-qubit gates.
  • Each iteration randomly modifies gate structure and post-processing, reoptimizes one-qubit gates, and accepts worse solutions with simulated-annealing probability.
  • Periodic compression searches for rewriteable gate subsequences that shorten the sequence without increasing cost.Compression can create room for additional gates while preserving the fixed total gate count.
  • Gate-sequence compression helps address low-lying local minima that arise during cost optimization.
  • Evaluating the cost for each training example scales exponentially with qubit number on a classical computer, although quantum hardware could evaluate individual contributions.This work evaluates the cost classically to study theoretical algorithms without device-specific noise.
  • The training-data size generally grows exponentially with data-qubit number, so numerical searches are restricted to small instances before manual generalization.
  • The gate-sequence search space is exponential in gate count, preventing systematic checking of all possibilities.The authors therefore use a heuristic search that they report as capable of finding solutions efficiently.

E. Generalization

The method tests fixed-size algorithm instances and increases the number of data qubits to study generalization. General algorithms are manually inferred from small instances because the search space grows rapidly with problem size.

  • An algorithm instance is declared when the cost is below 10^-6 for a fixed problem size.
  • Generalization is studied by increasing nD, the number of data qubits, and sometimes increasing ancilla-qubit or measurement resources.
  • The search space grows as nT^(2d), where nT = nD + nA is total qubit number and d is circuit gate count.
  • The authors manually recognized general patterns from algorithm instances and extended them to arbitrary problem size.They identify automated pattern recognition as future work.

III. MAIN RESULTS

The paper develops short-depth overlap algorithms for fully connected hardware with arbitrary one-qubit and CNOT gates. It reports an ancilla-based algorithm and a Bell-basis algorithm under different measurement resources, while noting generalization may be harder in other applications.

  • The main results are short-depth algorithms for quantifying state overlap on idealized, fully connected hardware.The considered gate set includes arbitrary one-qubit gates and CNOTs between all qubits.
  • With Swap Test resources, the minimum gate count is d = 8 for one-qubit states and d = 14 for n = 2, yielding the Ancilla-Based Algorithm.
  • Allowing measurements on all qubits gives zero cost at d = 2 for one-qubit states and d = 4 for n = 2, yielding the Bell-Basis Algorithm.The resulting BBA does not use the ancilla qubit.
  • Both general algorithms were inferred from their two smallest instances, but the authors expect generalization to be harder in other applications.

B. Ancilla-Based Algorithm

The Ancilla-Based Algorithm (ABA) uses a shorter circuit than the Swap Test while implementing a fundamentally different unitary. Its gate count scales linearly with input size.

  • One-qubit ABA: The one-qubit ABA uses 4 CNOT gates and 4 one-qubit gates, totaling 8 gates, with post-processing vector c = (1, −1).The post-processing measures the Pauli Z operator on the ancilla, as in the Swap Test.
  • One-qubit ABA: The ABA is fundamentally different from the Swap Test because its unitary has Schmidt rank 3 rather than the controlled-SWAP’s rank 2.Therefore, the ABA cannot be obtained from the Swap Test using local operations.
  • Generalized ABA: For n-qubit inputs, the ABA applies a repeating four-CNOT building block to each data-qubit pair, using 4n CNOTs and 6n + 2 total gates.The overall gate count grows linearly with the number of data qubits.
  • Relation to BBA: The Bell-Basis Algorithm (BBA) instead uses one CNOT and one Hadamard per qubit pair, with measurements on all qubits and post-processing vector c = (1, 1, 1, −1).The post-processing corresponds to measuring a controlled-Z expectation value.
  • Relation to BBA: The BBA’s paired gates can be parallelized, giving quantum depth two independent of problem size, while classical post-processing scales linearly with n.For near-term quantum computers, the paper favors linear classical processing over linearly growing quantum depth because of decoherence and gate infidelity.

D. Discussion

The paper relates ABA and BBA through a Toffoli-based conversion and adapts ABA to IBM and Rigetti hardware. Hardware-specific optimization adds gates, especially under weaker connectivity.

  • Equivalence of ABA and BBA: BBA’s two-qubit measurement and classical post-processing can be converted into a Toffoli gate targeting an ancilla, followed by ancilla measurement, yielding ABA after simplification.The equivalence extends straightforwardly from one-qubit to multi-qubit states.
  • Hardware adaptation: The machine-learning approach adapts ABA to hardware by optimizing with gate sets and connectivity matching IBM’s and Rigetti’s computers.BBA can be directly implemented on both architectures without connectivity concerns, aside from Rigetti’s controlled-Z-to-CNOT translation.
  • Hardware adaptation: IBM’s adapted ABA requires one additional Hadamard gate, whereas Rigetti’s adapted ABA requires an additional two-qubit gate and several additional one-qubit gates.These results are shown for IBM’s 5-qubit and Rigetti’s 19-qubit computers.
  • Hardware adaptation: Connectivity and native gate set affect performance: Rigetti’s lower connectivity produces longer, worse-performing algorithms, while IBM’s CNOT capability enables shorter circuits than controlled-Z.The comparison is specific to computing Tr(ρσ).

V. TESTING OUR ALGORITHMS

Experiments on IBM’s 5-qubit and Rigetti’s 19-qubit computers compare BBA, ABA, and the Swap Test using experimentally observed overlaps and RMS errors. ABA generally improves on the Swap Test with the same resources, while BBA performs especially well on Rigetti’s hardware.

  • Hardware experiments: The experiments evaluate BBA, ABA, and the Swap Test on IBM’s 5-qubit and Rigetti’s 19-qubit computers.The data use 49,152 runs per IBM point and 200,000 runs per Rigetti point.
  • Experimental comparison: On both computers, the Swap Test performed poorly, even for the tested single-qubit states.The authors expect performance to worsen as the state size grows.
  • Experimental comparison: ABA performed significantly better than the Swap Test while using the same resources, as shown by smaller RMS errors.RMS errors are reported in Table I for the data shown in Fig. 9.
  • Experimental comparison: BBA dramatically outperformed the other algorithms on Rigetti’s computer and performed roughly the same as ABA on IBM’s computer.Its short depth is identified as the reason for its relatively high accuracy.
  • Caveat: At some α values, including around α ≈π, the Swap Test performs better than ABA and BBA, but RMS error is presented as the better overall indicator.A fully decohered hardware could return zero overlap for every α, coincidentally giving the correct result at α = π.
  • Hardware dependence: Connectivity and native gate sets affect performance: Rigetti’s lower connectivity produces longer algorithms that overall perform worse than IBM’s.The comparison concerns algorithms discovered for the respective hardware architectures.

VI. CONCLUSIONS

The paper concludes that task-oriented machine learning can discover improved quantum algorithms beyond known circuits. Applied to state overlap, it yields a constant-depth BBA whose post-processing scales linearly with problem size.

  • VI. CONCLUSIONS: The automated approach improves well-known algorithms and produces more efficient circuits for state-overlap computation.The paper highlights applications including quantum machine learning, where the Swap Test appears as a subroutine.
  • VI. CONCLUSIONS: BBA has constant quantum circuit depth and significantly lower error than the Swap Test even for single-qubit states.Its post-processing complexity scales linearly with the number of input qubits.
  • Method: The method discovers algorithms by minimizing a cost function defined from training data representative of the desired computation.This task-oriented discovery is distinguished from compiling a previously known algorithm.
  • Method: The approach separates fixed quantum resources from optimized gate sequences and classical post-processing, then generalizes algorithms by recognizing patterns across problem sizes.The authors plan to automate this pattern-recognition step in future work.
  • Future direction: The method could be extended to learning on a quantum computer by outsourcing cost evaluation to that computer.The paper motivates this extension by noting the exponential overhead of classical quantum simulation.

Appendix A: Implementation details

The appendix details the Swap Test implementation generated by Rigetti’s compiler for its 19-qubit computer. It specifies the one-qubit gate decomposition and rotation parameters used in the circuit.

  • Circuit implementation: Rigetti’s compiler generated the Swap Test circuit for the company’s 19-qubit quantum computer.The circuit is shown in Fig. 10.
  • Gate decomposition: The implementation contains 22 one-qubit gates decomposed into rotations RZ(α) and pulses S.The appendix gives the corresponding gate forms and parameters.
  • Gate decomposition: The decomposition specifies U14 = U†, U18 = U†, and U21 = S.These assignments are part of the compiler-generated one-qubit gate sequence.
  • Gate decomposition: The appendix gives composite expressions for U15, U16, U17, U19, U20, and U22 using S, S†, and RZ rotations.The listed expressions include rotations with angles such as π/4, π, −3π/4, and −π/2.
  • Gate parameters: The rotation parameters are α1 ≃−0.6544π, α2 ≃0.7857π, α3 ≃0.1544π, and α4 ≃0.2143π.

Appendix B: Equivalence between ABA and BBA

The appendix establishes that BBA’s classical post-processing is equivalent to a quantum circuit using Toffoli gates followed by ancilla measurement. It also explains the equivalence through products of controlled-Z gates.

  • Equivalence construction: BBA post-processing is equivalent to a sequence of Toffoli gates followed by measuring Pauli Z on an ancilla qubit.This equivalence is illustrated in Fig. 11.
  • Equivalence construction: For multi-qubit inputs, the equivalence generalizes because the Toffoli gates are controlled by different qubits.
  • Controlled-Z formulation: BBA post-processing is equivalent to measuring the expectation value of a product of controlled-Z gates.The controlled-Z gate is symmetric, so control and target roles may be exchanged.
  • Controlled-Z formulation: The state immediately before measurement is represented by a 2N-qubit density matrix ρ, whose processed measurement outcome is compared with the Toffoli-based construction.
Loading 1803.04114v2…