Low Depth Phase Oracle Using a Parallel Piecewise Circuit

Abstract

We explore the important task of applying a phase $\exp (if(x))$ to a computational basis state $|x⟩$. The closely related task of rotating a target qubit by an angle depending on $f(x)$ is also studied. Such operations are key in many quantum subroutines, and frequently $f(x)$ can be well-approximated by a piecewise function; examples range from the application of diagonal Hamiltonian terms (such as the Coulomb interaction) in grid-based many-body simulation, to derivative pricing algorithms. Here we exploit a parallelisation of the piecewise approach so that all constituent elementary rotations are performed simultaneously, that is, we achieve a total rotation depth of one. Moreover, we explore the use of recursive catalyst `towers' to implement these elementary rotations efficiently. We find that strategies prioritising execution speed can achieve circuit depth as low as $O(\log n+\log S)$ for a register of $n$ qubits and a piecewise approximation of $S$ sections (presuming prior preparation of enabling resource states), albeit total qubit count then scales with $S$. In the limit of multiple repetitions of the oracle, we find that catalyst tower approaches have an $O(S\cdot n)$ T-count.

16 pages, table I updated

References in corpus (34)

• Quantum algorithm for solving linear systems of equations
• Quantum computational chemistry
• Quantum random access memory
• Hamiltonian Simulation by Qubitization
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Halving the cost of quantum addition
• Scaling silicon-based quantum computing using CMOS technology: State-of-the-art, Challenges and Perspectives
• QuEST and High Performance Simulation of Quantum Computers
• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
• Novel constructions for the fault-tolerant Toffoli gate
• Iterative Quantum Amplitude Estimation
• Efficient magic state factories with a catalyzed |CCZ> to 2|T> transformation
• A Threshold for Quantum Advantage in Derivative Pricing
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Lattice Surgery with a Twist: Simplifying Clifford Gates of Surface Codes
• Efficient synthesis of probabilistic quantum circuits with fallback
• Shorter gate sequences for quantum computing by mixing unitaries
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation
• Grid-based methods for chemistry simulations on a quantum computer
• Reducing the quantum computing overhead with complex gate distillation
• QuESTlink -- Mathematica embiggened by a hardware-optimised quantum emulator
• Black-box Hamiltonian simulation and unitary implementation
• Modelling semiconductor spin qubits and their charge noise environment for quantum gate fidelity estimation
• An efficient magic state approach to small angle rotations
• Quantum simulation of exact electron dynamics can be more efficient than classical mean-field methods
• Shorter quantum circuits via single-qubit gate approximation
• Derivative Pricing using Quantum Signal Processing
• Quantum Simulation of Realistic Materials in First Quantization Using Non-local Pseudopotentials
• Option pricing under stochastic volatility on a quantum computer
• Measuring Trotter error and its application to precision-guaranteed Hamiltonian simulations
• Cost-optimal single-qubit gate synthesis in the Clifford hierarchy
• Path integral simulation of exchange interactions in CMOS spin qubits
• Approximate real-time evolution operator for potential with one ancillary qubit and application to first-quantized Hamiltonian simulation

Cited by in corpus (2)

• Chemically Motivated Simulation Problems are Efficiently Solvable by a Quantum Computer
• Quantum algorithm for unstructured search of ranked targets