PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum-assisted quantum compiling

Sumeet Khatri, Ryan LaRose, Alexander Poremba, Lukasz Cincio, Andrew T. Sornborger, Patrick J. Coles

arXiv:1807.00800v5quant-ph

TL;DR

Near-term quantum computers require compilation that respects hardware constraints, but classical cost evaluation incurs exponential simulation overhead. QAQC evaluates overlap-based costs between target and trainable unitaries on a quantum computer, combining global and local overlaps. The paper proves classical hardness, develops short-depth evaluation circuits, and demonstrates compilation on IBM and Rigetti hardware plus simulations up to 9 qubits.

  • Problem

    NISQ compilation must account for limited qubits, connectivity, hardware-specific gate alphabets, and circuit depth while avoiding the exponential overhead of classical quantum-dynamics simulation.

  • Method

    QAQC variationally trains a gate sequence using a quantum-computed cost that combines global and local overlaps between a target unitary U and trainable unitary V.

  • Results

    QAQC was demonstrated on IBM and Rigetti hardware for one-qubit native-gate compilation and simulated successfully for unitaries up to 9 qubits, with reported noise resilience.

  • Takeaways & Limitations

    QAQC provides a quantum-assisted route to compiling larger-scale gate sequences and supports applications including depth compression, black-box uploading, noise mitigation, and benchmarking.

  • Takeaways & Limitations

    The CHST cost can exhibit barren plateaus even for depth-one ansätze, with exponentially vanishing gradients and failed direct training for n ≥ 6 qubits; CLHST resolved the tested cases up to 9 qubits.

Abstract

from arXiv · show

Compiling quantum algorithms for near-term quantum computers (accounting for connectivity and native gate alphabets) is a major challenge that has received significant attention both by industry and academia. Avoiding the exponential overhead of classical simulation of quantum dynamics will allow compilation of larger algorithms, and a strategy for this is to evaluate an algorithm's cost on a quantum computer. To this end, we propose a variational hybrid quantum-classical algorithm called quantum-assisted quantum compiling (QAQC). In QAQC, we use the overlap between a target unitary $U$ and a trainable unitary $V$ as the cost function to be evaluated on the quantum computer. More precisely, to ensure that QAQC scales well with problem size, our cost involves not only the global overlap ${\rm Tr} (V^\dagger U)$ but also the local overlaps with respect to individual qubits. We introduce novel short-depth quantum circuits to quantify the terms in our cost function, and we prove that our cost cannot be efficiently approximated with a classical algorithm under reasonable complexity assumptions. We present both gradient-free and gradient-based approaches to minimizing this cost. As a demonstration of QAQC, we compile various one-qubit gates on IBM's and Rigetti's quantum computers into their respective native gate alphabets. Furthermore, we successfully simulate QAQC up to a problem size of 9 qubits, and these simulations highlight both the scalability of our cost function as well as the noise resilience of QAQC. Future applications of QAQC include algorithm depth compression, black-box compiling, noise mitigation, and benchmarking.

1 Introduction

QAQC addresses quantum compiling for NISQ devices by evaluating a trainable unitary’s cost on a quantum computer. Its cost combines global and local overlaps, with short-depth evaluation circuits and a proof of classical hardness.

  • Motivation: NISQ devices impose constraints on qubit count, connectivity, native gate alphabets, and circuit depth, motivating quantum compiling.These constraints can make adapted algorithms differ substantially from textbook versions.
  • QAQC approach: QAQC compiles a possibly unknown target unitary into a trainable quantum gate sequence while computing the cost directly on a quantum computer.The authors argue this avoids the exponential classical simulation overhead for cost evaluation.
  • Cost function: QAQC’s cost is designed to be faithful, quantum-computable, operationally meaningful, and scalable with problem size.These criteria guide the construction of the global-local cost.
  • Cost function: The proposed cost combines a global overlap with localized overlaps that quantify agreement between target and trainable unitaries on individual qubits.The global Hilbert-Schmidt overlap alone does not scale well with problem size.
  • Technical results: The authors introduce short-depth circuits for evaluating cost terms and prove that the cost is DQC1-hard, ruling out efficient classical evaluation under stated complexity assumptions.The circuits avoid controlled versions of the target and trainable unitaries and implement them in parallel.
  • Demonstrations: QAQC was demonstrated on IBM and Rigetti hardware for one-qubit native-gate compilation and simulated for unitaries up to 9 qubits.The noisy simulations exhibited resilience to noise, while the larger simulations supported the scalability of the cost function.

2 Applications of QAQC

QAQC supports applications ranging from hardware-aware depth compression and black-box uploading to noise-tailored algorithms and benchmarking. These applications use trainable circuits to adapt target unitaries to hardware constraints or noise conditions.

  • Depth compression: QAQC can shorten gate sequences by accounting for the connectivity and native gate alphabet of a specific NISQ computer.The paper states that this depth compression goes beyond classical compiler capabilities.
  • Depth compression: For quantum Fourier transforms, QAQC takes a holistic approach rather than locally compiling each textbook gate, allowing it in principle to learn an optimal hardware-specific sequence.Classical compilers may produce suboptimal depth because they begin from the textbook structure.
  • Black-box uploading: QAQC can convert an analog black-box unitary such as e^(-iHt) into a gate sequence for a digital quantum computer.This application is called black-box uploading.
  • Noise-tailored algorithms: With pristine and noisy qubits available, QAQC can learn one-qubit corrections around a CNOT so noisy hardware effectively implements the target CNOT.The resulting algorithms are described as noise-tailored because they are robust to the noise process on the noisy qubits.
  • Benchmarking: For benchmarking, QAQC uses a unitary implemented on noisy qubits to learn the equivalent unitary on pristine qubits, thereby learning the noisy qubits’ noise model.This is the counterpart to training a noise-tailored algorithm.

3 The QAQC Algorithm

QAQC trains a native-gate unitary V to approximate a target unitary U by jointly optimizing gate structures and continuous parameters. It combines global and local overlap costs, using local terms to improve scalability and gradient behavior for larger systems.

  • Objective: QAQC returns a native-gate sequence V that approximately reproduces a possibly unknown target unitary U, up to a global phase.The trainable sequence length L can be increased to obtain progressively better approximate compilations.
  • Optimization: The optimization jointly searches discrete gate structures and continuous gate parameters using a hybrid quantum-classical procedure.Small systems can use structure updates, while larger systems use a fixed ansatz.
  • Cost design: For large problems, the cost is a weighted average of the global HST cost and localized overlaps measured with respect to individual qubits.The weight q controls the contribution of the global cost, while local terms require only two-qubit measurements per local cost.
  • Scalability: The global cost can become exponentially fragile because random trainable unitaries make the global overlap nearly vanish as the number of qubits grows.This produces cost landscapes near one with vanishing gradients, whereas averaging local overlaps avoids the product suppression.
  • Cost properties: The local cost is faithful: it reaches zero if and only if U and V differ only by a global phase.The combined cost retains an operational connection to the average fidelity between the target and compiled unitaries.

4 Cost evaluation circuits

The paper introduces short-depth quantum circuits for evaluating QAQC’s global and local costs. The HST measures a global unitary overlap, while the LHST measures corresponding two-qubit local overlaps with the same circuit depth.

  • Hilbert-Schmidt Test: The HST estimates the global overlap by preparing entanglement, applying U and V* in parallel, and measuring the Bell-basis |Φ+⟩ outcome.The all-zero outcome probability is (1/d^2)|Tr(V†U)|^2.
  • Circuit depth: The HST circuit avoids controlled versions of U and V and applies them in parallel to achieve short depth.Its overall depth is determined by whichever of U or V* has the larger depth when the unitary depth dominates.
  • Local Hilbert-Schmidt Test: The LHST modifies the HST by measuring only a corresponding pair of qubits, Aj and Bj, rather than all 2n qubits.Each local measurement probability gives an entanglement fidelity used to define the local cost.
  • Cost definitions: The local cost averages the probabilities that the measured qubit pairs are not in |00⟩, whereas the global cost uses the probability that all qubits are not jointly zero.The two costs satisfy bounds relating local and global deviations.
  • Properties: Both HST and LHST have the same circuit depth, despite LHST measuring fewer qubits.The LHST cost is faithful: it vanishes exactly when U and V agree up to a global phase.

5 Computational complexity of cost evaluation

The paper argues that efficiently evaluating QAQC’s global and local costs classically is computationally hard. Both cost-approximation problems are shown to be DQC1-hard, implying a classical barrier under standard complexity assumptions.

  • Hardness framework: The analysis uses the DQC1 model and known hardness results for trace estimation to study classical approximation of CHST and CLHST.The goal is to establish hardness for inverse-polynomial precision.
  • Consequence: Efficient classical approximation of either cost with inverse-polynomial precision would imply a collapse of the polynomial hierarchy to its second level.The paper presents this as a consequence of the DQC1 simulation results under the stated complexity assumptions.
  • Global cost: Approximating CHST(U,V) to ϵ = O(1/poly(n)) precision is DQC1-hard for polynomial-size quantum circuits.The unitaries are represented by 2^n × 2^n matrices.
  • Local cost: Approximating CLHST(U,V) to ϵ = O(1/poly(n)) precision is likewise DQC1-hard for polynomial-size quantum circuits.The result applies to the local cost as well as the global cost.

6 Small-scale implementations

QAQC was implemented on IBM and Rigetti hardware, where it compiled one-qubit gates into hardware-native sequences, and on Rigetti’s simulator, where it found short decompositions for one- and two-qubit gates.

  • Hardware implementations: QAQC was implemented on IBMQX4, IBMQX5, and Rigetti’s 8Q-Agave quantum computers, with circuit depth defined relative to each device’s native gate alphabet.The IBM devices support Rx(π/2), Rz(θ), and topology-constrained CNOT gates, while Rigetti supports Rx(±π/2), Rz(θ), and topology-constrained CZ gates.
  • Hardware implementations: On IBMQX4, all four one-qubit gates converged below cost 0.1, but none reached the 10^-2 tolerance because of sampling and device errors.The compiled sequences included Rz(θ) for the identity and T gates and Rx(π/2)Rx(π/2) for X.
  • Hardware implementations: On IBMQX5, X compiled to Rx(π/2)Rx(π/2), while H compiled to Rx(π/2)Rz(π/2)Rx(π/2), with optimized angles θ = −0.03π for 1 and θ = 0.23π for T.Angle standard deviations across roughly 10 independent runs were about 0.05π.
  • Quantum simulator: In simulation, QAQC reproduced the depth-three CNOT decomposition of SWAP and discovered shorter-than-conventional decompositions for CZ and QFT2 in Rigetti’s gate alphabet.The SWAP cost vanishes at depth three, whereas depths one and two cannot achieve zero cost; the reported circuit equalities hold up to global phase.

7 Larger-scale implementations

Larger-scale simulations tested QAQC on tensor-product and fully entangling unitaries up to nine qubits. Local-overlap training was more reliable than direct global-overlap training from six qubits onward, including under realistic noise.

  • Experimental setup: QAQC was evaluated on tensor-product and entangling target unitaries, with trainable ansätze using corresponding parameterized structures and gradient-based optimization.The study used noiseless and IBMQX5-matched noisy simulators to examine scaling and noise effects.
  • Noiseless implementations: In the tensor-product example, CHST and CLHST reached the global minimum through 5 qubits, while for n ≥ 6 CHST sometimes stalled near one and CLHST still converged.The gradient threshold was 10^-3 for four consecutive iterations; angles learned with CLHST also minimized CHST.
  • Noiseless implementations: In the entangling example, direct CHST training failed for n ≥ 6, whereas CLHST reached the global minimum for n = 6 and n = 8 and also minimized CHST.This reproduced the qualitative advantage of local-cost training observed in the tensor-product example.
  • Noisy implementations: With IBMQX5-matched noise, both costs converged through 5 qubits but converged to values above zero because of noise.The noise model included T1, T2, gate, and measurement errors.
  • Noisy implementations: For n ≥ 6 under noise, CHST failed to converge to a local minimum, while CLHST converged in every case and learned angles corresponding to the noiseless optimum.Evaluating noiseless CHST at angles obtained from noisy CLHST optimization produced zero-valued curves at the local minima.

8 Discussion

QAQC successfully compiled small gates on hardware and trained up to 9-qubit unitaries in simulation, but optimization faces distinct barren-plateau and hardware-noise challenges. The localized cost CLHST overcame the training failure observed for CHST in larger examples, while noisy simulations still recovered correct parameters.

  • QAQC compiled one-qubit gates on IBM and Rigetti hardware without prior assumptions about gate structure or parameters.
  • 9-qubit QAQC implementations succeeded on both noiseless and noisy simulators, highlighting cost-function scalability and apparent noise resilience.
  • Barren Plateaus: Gradient-based optimization can suffer barren plateaus for deep random ansätze, motivating short-depth or application-specific ansätze.
  • Barren Plateaus: CHST can exhibit exponentially vanishing gradients even for depth-one, single-parameter ansätze, preventing direct training for n ≥ 6 in tested cases.
  • Barren Plateaus: CLHST resolved the observed CHST training failure in all attempted cases through n = 9, despite lacking direct operational meaning.
  • Effect of Hardware Noise: HST noise grows with entangling-gate, connectivity, circuit-depth, coherence, and readout constraints as problem size increases.The HST uses 2n qubits, n CNOT gates for entangled-state preparation, and measurements scaling linearly with qubit number.
  • Effect of Hardware Noise: Realistic IBMQX5 noise affected all LHST circuit elements, yet QAQC recovered the correct unitary V in the reported implementations.
  • Effect of Hardware Noise: Noise significantly changed CLHST cost values without shifting the parameter-space location of the global minimum in the reported examples.

9 Conclusions

The paper presents QAQC as a quantum-assisted compilation methodology that evaluates gate-sequence costs on quantum computers and demonstrates it on hardware and 9-qubit simulators. Its technical contributions include scalable overlap-based costs, short-depth evaluation circuits, a classical-hardness result, and optimization methods.

  • QAQC addresses quantum compilation under NISQ constraints by using a quantum computer to evaluate how closely a gate sequence matches a target.
  • QAQC compiled various one-qubit gates into IBM and Rigetti native gate alphabets and was implemented on noiseless and noisy simulators for simple 9-qubit unitaries.
  • The cost combines global and local overlaps, satisfies faithfulness, quantum-computability, operational-meaning, and scalability criteria, and is DQC1-hard to evaluate classically.
  • Short-depth circuits compute the cost, while the paper also provides gradient-free and gradient-based optimization methods, including a generalized Power of One Qubit circuit.
  • Noisy 9-qubit simulations using realistic IBMQX5 parameters obtained the correct parameters for V, with noise resilience identified for future study.
  • QAQC’s central application is making quantum computers more useful through algorithm depth compression, including potential use in fault-tolerant computing.

A Remark on implementation of V ∗

Implementing V* may require a small classical translation into the native gate alphabet, and a non-conjugation-closed alphabet can increase circuit depth by at most a constant factor.

  • The cost-evaluation circuits require executing the complex conjugate V* rather than V itself on the quantum computer.
  • A small classical compiler translates the conjugated one- and two-qubit gates into the hardware’s native alphabet without exponential overhead.
  • If the native alphabet is not closed under complex conjugation, conjugation can increase gate-sequence depth, but only by at most a constant factor.

B Faithfulness of LHST cost function

The LHST cost function is faithful: it vanishes exactly when the target and trainable unitaries agree up to a global phase. Its local costs are bounded by the global cost, while the global cost is bounded by their sum.

  • CLHST(U, V) = 0 if and only if U = V up to a global phase.
  • The proof rewrites U = V as W := UV† = 1 and shows that zero local cost forces every induced channel Ej to be the identity.
  • Applying operator-Schmidt decompositions across successive qubit cuts shows that identity channels sequentially factor W into identities on all qubits.
  • The converse follows because W = 1 implies each Ej is the identity, yielding U = V as required.
  • CLHST(U, V) ≤ CHST(U, V) ≤ nCLHST(U, V), relating the local and global Hilbert-Schmidt costs.

D Proofs of complexity theorems

The paper proves that approximating both the global and local Hilbert-Schmidt cost functions is DQC1-hard to inverse-polynomial precision. These reductions connect cost evaluation to estimating traces or acceptance probabilities in the one-clean-qubit model.

  • Approximating CHST(U, V) to ε = O(1/poly(n)) is DQC1-hard for poly(n)-sized quantum circuits.
  • The global-cost reduction encodes a DQC1 acceptance probability into the absolute trace of a unitary and then into CHST(U′, 1).
  • The reduction uses a short-depth circuit whose unitary trace matches a projected non-unitary operator up to a factor of 4.
  • Approximating CLHST(U, V) to ε = O(1/poly(n)) is also DQC1-hard.
  • The local-cost reduction extracts Tr(U′) from two evaluations, CLHST(U1, 1) and CLHST(U2, 1), followed by elementary post-processing.

E Gradient-free optimization method

QAQC’s gradient-free method combines quantum cost estimation with classical continuous optimization. For larger systems it uses a weighted global-and-local cost, while sampling controls the cost-estimation overhead.

  • The small-scale method optimizes CHST(U, Vk(α)) over continuous gate parameters using gradient-free classical optimization.
  • Each objective evaluation estimates the Hilbert-Schmidt cost by repeatedly running the HST on U and Vk(α).
  • For larger systems, the method replaces CHST with Cq = qCHST + (1 − q)CLHST and evaluates the local HST for every qubit.
  • O(1/δ^2) quantum-computer calls estimate the cost, with δ = 1/√nshots determined by sampling precision.
  • An alternative multi-scale bisection method starts from four uniformly spaced angles and refines candidate rotation angles to reduce objective evaluations.

F Gradient-based optimization method

The gradient-based method evaluates a real-overlap cost and its gradients with the Power of Two Qubits circuit, then uses classical gradient descent to optimize rotation parameters. The approach is demonstrated on a simulator but is limited on current hardware by controlled-unitary errors.

  • F.2 Gradient-based optimization via the POTQ: The gradient-based approach optimizes continuous parameters using a cost function and gradient evaluated by quantum circuits within classical optimization.
  • F Gradient-based optimization method: Any one- or two-qubit unitary can use the fixed rotation-based decompositions supporting parameter-wise gradient evaluation.
  • F.1 The Power of Two Qubits: CPOTQ(U, V) vanishes exactly when U = V, but unlike CHST it penalizes differences in global phase.
  • F.1 The Power of Two Qubits: The Power of Two Qubits circuit computes the real and imaginary parts of ⟨V, U⟩ using parallel controlled-U and anticontrolled-V^T operations.
  • F.2 Gradient-based optimization via the POTQ: Each gradient component is obtained by adding the corresponding Pauli gate to the trainable sequence and running POTQ.
  • F.2 Gradient-based optimization via the POTQ: O(NTL/δ^2) cost-evaluation calls are required for Algorithm 3 under the stated sampling and optimization parameters.
  • F Gradient-based optimization method: Controlled-unitary decoherence, gate infidelity, and readout errors prevented implementing the gradient-based method on current quantum devices.
Loading 1807.00800v5…