Approximate Quantum Circuit Synthesis using Block-Encodings

Abstract

One of the challenges in quantum computing is the synthesis of unitary operators into quantum circuits with polylogarithmic gate complexity. Exact synthesis of generic unitaries requires an exponential number of gates in general. We propose a novel approximate quantum circuit synthesis technique by relaxing the unitary constraints and interchanging them for ancilla qubits via block-encodings. This approach combines smaller block-encodings, which are easier to synthesize, into quantum circuits for larger operators. Due to the use of block-encodings, our technique is not limited to unitary operators and can also be applied for the synthesis of arbitrary operators. We show that operators which can be approximated by a canonical polyadic expression with a polylogarithmic number of terms can be synthesized with polylogarithmic gate complexity with respect to the matrix dimension.

References in corpus (16)

• Quantum Computing in the NISQ era and beyond
• Elementary gates for quantum computation
• Quantum algorithm for solving linear systems of equations
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Synthesis of Quantum Logic Circuits
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Quantum-assisted quantum compiling
• Quantum-state preparation with universal gate decompositions
• A universal quantum circuit for two-qubit transformations with three CNOT gates
• Efficient synthesis of universal Repeat-Until-Success circuits
• Hamiltonian Simulation Using Linear Combinations of Unitary Operations
• Compiling quantum algorithms for architectures with multi-qubit gates
• QFAST: Quantum Synthesis Using a Hierarchical Continuous Circuit Space
• Compiling basic linear algebra subroutines for quantum computers

Cited by in corpus (12)

• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation
• Numerical analysis of quantum circuits for state preparation and unitary operator synthesis
• Quantum algorithms for scientific computing
• Exploring the optimality of approximate state preparation quantum circuits with a genetic algorithm
• Quantum circuit synthesis via a random combinatorial search
• QGo: Scalable Quantum Circuit Optimization Using Automated Synthesis
• Numerical circuit synthesis and compilation for multi-state preparation
• Quantum Algorithm for Estimating Betti Numbers Using Cohomology Approach
• Scalable Quantum Computational Science: A Perspective from Block-Encodings and Polynomial Transformations
• Quantum Approximation of Normalized Schatten Norms and Applications to Learning
• Quantum Algorithm For Solving Nonlinear Algebraic Equations