Session Z73: Quantum algorithm benchmarking and validation

Efficient decomposition of multi-qubit gates

Applications in the NISQ era are restricted by the coherence time of the qubits thereby restricting the depth of the quantum circuit. Additionally, every hardware platform has limitations on the available set of hardware native gates. We show how to efficiently decompose a multi-qubit gate into native two-qubit gates minimizing both the depth and the number of two-qubit gates. Given a computational model, we argue that the technique is optimal in terms of the number of hardware native gates and the overall depth of the decomposition. Starting from decompositions for 1-d and star Hardware graphs, we generalize the procedure to any generic Hardware graph and provide exact expressions for the depth and number of two-qubit gates of the circuit. Furthermore, we show how to efficiently combine the decomposition of multi-qubit gates for a few specific problems.   

Random circuit sampling revisited: Part I

Random circuit sampling (RCS) is the leading benchmark for quantum computers to achieve performance beyond classical computing capability. Ever since the first proposal in 2016 and the first experimental demonstration in 2019, there have been continued investigations of both experimental and theoretical RCS. Meanwhile, it has also been challenged by the advancement of classical algorithms. We will cover progress on RCS on both fronts.   

Random circuit sampling revisited: Part II

Random circuit sampling (RCS) is the leading benchmark for quantum computers to achieve performance beyond classical computing capability. Ever since the first proposal in 2016 and the first experimental demonstration in 2019, there have been continued investigations of both experimental and theoretical RCS. Meanwhile, it has also been challenged by the advancement of classical algorithms. We will cover progress on RCS on both fronts.   

Improved Simulations of Random Quantum Circuits

In the past few years, numerical techniques to classically simulate quantum circuits have steadily improved. In my presentation, I will review some of our latest advances and present numerical results on our improved simulations of Sycamore-like circuits.   

Quantum Routing with Teleportation

We study the problem of implementing arbitrary permutations of qubits under interaction constraints in quantum systems that allow for arbitrarily fast local operations and classical communication (LOCC). In particular, we show examples of speedups over swap-based and more general unitary routing methods by distributing entanglement and using LOCC to perform quantum teleportation. We further describe an example of an interaction graph for which teleportation gives a logarithmic speedup in the worst-case routing time over swap-based routing. We also study limits on the speedup a orded by quantum teleportation|showing an O(√(N logN)) upper bound on the separation in routing time for any interaction graph and give tighter bounds for some common classes of graphs.   

Inteference Tomography

Processing quantum data on a quantum computer can, on certain tasks, offer significant improvement over a purely classical scenario where a classical computer is used to process classical data from conventional measurements. More specifically, recent work has shown that by interfering and measuring two copies of any target state it is possible to estimate the absolute value of all Pauli strings’ expectation values with a sample complexity that is constant with respect to the number of qubits. We propose a modified version of the same scheme that computes the sign of all expectation values. For classes of states where the magnitude of Pauli string expectation values does not decrease as the number of qubits increases, the constant sample complexity is preserved. Once the sign of all expectation values has been learned, the target state can be fully reconstructed.   

Co-Designing the QPU's topology for a quantum algorithm

While the efforts for fault-tolerant Quantum Processing Units (QPUs) advance, several strategies are developed to pursue early quantum advantage making use of Noisy Intermediate-Scale Quantum devices. One of these strategies is the Co-Design of quantum hardware and algorithms, through the design and fabrication of Quantum Application Specific Integrated Chips (QuASICs). [1]

 

Transpiling a quantum algorithm to a QPU with limited connectivity introduces the need of SWAP gates and a deeper circuit, producing more errors in the computation. In this talk, we discuss recent progress on Co-Designing a QPU’s topology (its physical two-qubit connections) to a specific algorithm’s structure (its two-qubit gates), showing how this can reduce the number of required SWAP gates, as well as the extra depth introduced by them. We further quantify the effects of choosing a particular QPU topology on generic quantum algorithm performance, and show how to adapt this quantitative study to design and analyze QuASICs. To illustrate this, we discuss the design of a QuASIC for a specific quantum algorithm, and analyze its performance compared to two-dimensional lattice QPUs, such as the square lattice.

 

[1] M.G. Algaba et al., “Co-Design quantum simulation of nanoscale NMR” (2022), arXiv:2202.05792

[2] B. Lu et al., “Special-Purpose Quantum Processor Design” (2021), arXiv:2102.01228   

Clifford+T-gate decomposition with limited number of T gates and performance of Unitary Coupled Cluster ansatz in early-FTQC era

In this work, we propose a method to provide a Clifford+T-gate decomposition of a given quantum gate when the maximum number of T gates available is restricted especially in an early stage of fault-tolerant quantum computation (FTQC). Fault-tolerant realization of universal gates, e.g., Clifford+T gates, is essential for FTQC. Solovay-Kitaev (SK) theorem evaluated the number of T gates needed to obtain a target quantum gate within desired accuracy. On the other hand, in an early FTQC era, we likely need to implement a given quantum circuit with a limited number of T gates. Now, the question is, "what is the best accuracy we can achieve only using the available number of T gates?" We propose a gate-decomposition method based on the algorithm by Ross and Selinger [Quantum Inf. Comput. 16(11-12), 2016], which yields a decomposition of a single qubit z-rotation with the smallest error under a limited budget of T gates. In addition, we propose to average the effects of SK error, the error caused by the SK decomposition, when the given circuit is sufficiently large. With our averaging method, we may model the effects of SK error by the single-qubit depolarizing channel. We also numerically examine these proposals using the unitary coupled cluster (UCC) ansatz, and estimate the number of T gates needed to simulate an approximate ground state of molecules by the UCC ansatz within a given accuracy.

    

Universal Parity Quantum Computing

In this talk, I will present a universal gate set for quantum computing with all-to-all connectivity and intrinsic robustness to bit-flip errors based on the parity encoding [1,2]. The results show that logical CPhase gates and R_Z rotations can be implemented in the parity encoding with single-qubit operations. Together with logical R_X rotations, implemented via nearest-neighbor CNOT gates and an R_X  rotation, these form a universal gate set. As the CPhase gate requires only single qubit rotations, the proposed scheme has advantages for several cornerstone quantum algorithms. I will demonstrate the applicability of the universal gate set in the parity encoding, which is a dual to the standard gate model, by exploring several quantum gate algorithms such as the Quantum Fourier Transform and Quantum Addition. Embedding these algorithms in the parity encoding reduces the circuit depth as compared to conventional gate-based implementations while keeping the multi-qubit gate counts comparable. I will further propose simple implementations of multi-qubit gates in tailored encodings and an efficient strategy to prepare graph states.

[1] Universal Parity Quantum Computing, Michael Fellner, Anette Messinger, Kilian Ender, and Wolfgang Lechner, accepted in PRL, preprint arxiv:2205.09505 (2022).

[2] Applications of Universal Parity Quantum Computation, Michael Fellner, Anette Messinger, Kilian Ender, and Wolfgang Lechner, accepted in PRA, preprint arXiv:2205.09517 (2022).   

Numerical analysis of quantum circuits for state preparation and unitary operator synthesis

We perform optimal-control-theory calculations to determine the minimum number of two-qubit CNOT gates needed to perform quantum state preparation and unitary operator synthesis for few-qubit systems. By considering all possible gate configurations, we determine the maximum achievable fidelity as a function of quantum circuit size. This information allows us to identify the minimum circuit size needed for a specific target operation and enumerate the different gate configurations that allow a perfect implementation of the operation. We find that there are a large number of configurations that all produce the desired result, even at the minimum number of gates. We also show that the number of entangling gates can be reduced if we use multi-qubit entangling gates instead of two-qubit CNOT gates, as one might expect based on parameter counting calculations. In addition to treating the general case of arbitrary target states or unitary operators, we apply the numerical approach to the special case of synthesizing the multi-qubit Toffoli gate. This approach can be used to investigate any other specific few-qubit task and provides insight into the tightness of different bounds in the literature.   

Advantages and limitations of quantum routing

The Swap gate is a ubiquitous tool for moving information on quantum hardware, yet it can be considered a classical operation because it does not entangle product states. Genuinely quantum operations could outperform Swap for the task of permuting qubits within an architecture, which we call routing. We consider quantum routing in two models: (1) allowing arbitrary two-qubit unitaries, or (2) allowing Hamiltonians with norm-bounded interactions. We lower bound the circuit depth or time of quantum routing in terms of spectral properties of graphs representing the architecture interaction constraints, and give a generalized upper bound for all simple connected n-vertex graphs. In particular, we give conditions for a superpolynomial classical-quantum routing separation, which exclude graphs with a small spectral gap and graphs of bounded degree. Finally, we provide examples of a quadratic separation between gate-based and Hamiltonian routing models with a constant number of local ancillas per qubit and of an Ω(n) speedup if we also allow fast local interactions.   

Optimizing quantum circuits with Riemannian gradient flow

Variational quantum algorithms are a promising class of algorithms that can be performed on currently available quantum computers. In most settings, the free parameters of a variational circuit are optimized using a classical optimizer that updates parameters in Euclidean geometry. Since quantum circuits are elements of the special unitary group, we can consider an alternative optimization perspective that depends on the structure of this group. In this work, we investigate a Riemannian optimization scheme over the special unitary group and we discuss its implementation on a quantum computer. We illustrate that the resulting Riemannian gradient-flow algorithm has favorable optimization properties for deep circuits and that an approximate version of this algorithm can be performed on near-term hardware.   

Quantum Algorithm for unscrambling quantum information

In a seminal paper[JHEP09(2007)120], Hayden and Preskill showed that information can be retrieved from a black hole that is sufficiently scrambling, assuming that the retriever has perfect control of the emitted Hawking radiation and perfect knowledge of the internal dynamics of the black hole. In our work, we show that for t−doped Clifford black holes - that are, black holes modeled by random Clifford circuits polluted with an amount t of non-Clifford resources - a randomized Clifford decoder can be learned using an algorithm requiring O(poly(n)exp(t)) queries access to the t-doped Clifford black hole. Decoder that, with probability 1-2^t-2n_C, retrieves the information with fidelity ≥ 1-2^n_A+t-2n_D. Consequently, with a suitable choice of n_C and n_D, one can retrieve the information scrambled by O(n)-doped Clifford circuits with overwhelming probability.

    

Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle

Recent work shows that quantum signal processing (QSP) and its lifted version, quantum singular value transformation (QSVT), unify and improve the presentation of most quantum algorithms. QSP/QSVT characterize the ability, by alternating ansätze, to obliviously transform the singular values of subsystems of unitary matrices by polynomial functions; these algorithms are stable and well-understood. That said, QSP/QSVT require consistent access to a single oracle, saying nothing about computing joint properties of two oracles; these can be far cheaper to determine given an ability to pit oracles against one another coherently.

This work introduces a corresponding theory of QSP over multiple variables: M-QSP. Surprisingly, despite the non-existence of the fundamental theorem of algebra for multivariable polynomials, there exist necessary and sufficient conditions under which a desired stable multivariable polynomial transformation is possible. Moreover, the classical subroutines used by QSP protocols survive in the multivariable setting for non-obvious reasons, and remain numerically stable. Up to a well-defined conjecture, we give proof that the family of achievable multivariable transforms is as loosely constrained as could be expected. The unique ability of M-QSP to obliviously approximate joint functions of multiple variables coherently leads to novel speedups incommensurate with those of other quantum algorithms, and provides a bridge from quantum algorithms to algebraic geometry.   

Quantum Kernel Methods for Supervised Machine Learning

Kernel methods are a subset of machine learning algorithms that learn patterns in the input data by using a positive-definite similarity measure between pairs of points. In this context, the output of such a similarity measure (or kernel function) corresponds to an inner product on vectors obtained through a feature map on the input data. A feature map itself, however, need not be explicitly computed. Kernel methods are especially elegant in the sense that any kernel function, as a black-box pairwise similarity measure, can be substituted into the algorithm in a modular way. Following the advance of quantum computing into the so-called noisy intermediate-scale (NISQ) era, several quantum circuits have been proposed as classically intractable kernels for supervised learning. While the utility of quantum kernels has been demonstrated for specifically structured data, open questions remain regarding their general role in machine learning. Operating within constraints of presently available quantum hardware, this work examines two promising avenues for NISQ-compatible applications. First, we consider hybrid multi-kernels consisting of quantum-quantum and quantum-classical combinations as a means of improving the classification performance of quantum support-vector machines. Next, by leveraging an existing method for non-Trotterized time evolution in quantum circuits, we employ a time-dependent quantum kernel to classify time series data in a novel application. Together, these results culminate in a roadmap for the continuing development of near-term quantum kernel methods.