Quantum measurements and the Abelian Stabilizer Problem

Abstract

We present a polynomial quantum algorithm for the Abelian stabilizer problem which includes both factoring and the discrete logarithm. Thus we extend famous Shor's results. Our method is based on a procedure for measuring an eigenvalue of a unitary operator. Another application of this procedure is a polynomial quantum Fourier transform algorithm for an arbitrary finite Abelian group. The paper also contains a rather detailed introduction to the theory of quantum computation.

22 pages, LATEX

References in corpus (1)

• Elementary gates for quantum computation

Cited by in corpus (213)

• Fault-tolerant quantum computation by anyons
• A variational eigenvalue solver on a quantum processor
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Quantum Amplitude Amplification and Estimation
• Quantum Algorithms Revisited
• The Variational Quantum Eigensolver: a review of methods and best practices
• Entanglement-free Heisenberg-limited phase estimation
• Information and Computation: Classical and Quantum Aspects
• Efficient Simulation of Quantum Systems by Quantum Computers
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Simulating chemistry using quantum computers
• Quantum Metropolis Sampling
• An Exact Quantum Polynomial-Time Algorithm for Simon's Problem
• OpenQASM 3: A broader and deeper quantum assembly language
• Amplitude estimation without phase estimation
• Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
• Efficient Bayesian Phase Estimation
• A perspective on the current state-of-the-art of quantum computing for drug discovery applications
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Experimental Bayesian Quantum Phase Estimation on a Silicon Photonic Chip
• Quantum Lower Bounds by Polynomials
• Quantum phase estimation of multiple eigenvalues for small-scale (noisy) experiments
• Is the Trotterized UCCSD Ansatz chemically well-defined?
• Improved quantum capacity bounds of Gaussian loss channels and achievable rates with Gottesman-Kitaev-Preskill codes
• Simulating chemistry efficiently on fault-tolerant quantum computers
• Application-Oriented Performance Benchmarks for Quantum Computing
• Quantum query complexity of state conversion
• Quantum error mitigation as a universal error-minimization technique: applications from NISQ to FTQC eras
• From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
• Quantum factoring, discrete logarithms and the hidden subgroup problem
• A comparison of the Bravyi-Kitaev and Jordan-Wigner transformations for the quantum simulation of quantum chemistry
• Electron-Phonon Systems on a Universal Quantum Computer
• Encoding a Qubit into a Cavity Mode in Circuit-QED using Phase Estimation
• Quantum circuits cannot control unknown operations
• Preparing ground states of quantum many-body systems on a quantum computer
• Quantum Approximate Counting, Simplified
• Anyons from non-solvable finite groups are sufficient for universal quantum computation
• qHiPSTER: The Quantum High Performance Software Testing Environment
• Quantum Algorithm for Spectral Measurement with Lower Gate Count
• A Jastrow-type decomposition in quantum chemistry for low-depth quantum circuits
• A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance
• Fermionic quantum processing with programmable neutral atom arrays
• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• An Introduction to Quantum Complexity Theory
• Quantum walks can find a marked element on any graph
• Prime factorization using quantum annealing and computational algebraic geometry
• Efficient step-merged quantum imaginary time evolution algorithm for quantum chemistry
• Efficient Quantum Transforms
• Exact and efficient Lanczos method on a quantum computer
• Minimizing estimation runtime on noisy quantum computers
• Quantum computing of the ${}^6$Li nucleus via ordered unitary coupled clusters
• Low depth algorithms for quantum amplitude estimation
• The Los Alamos Trapped Ion Quantum Computer Experiment
• Liquid state NMR simulations of quantum many-body problems
• Variational approaches to constructing the many-body nuclear ground state for quantum computing
• Quantum Fourier Transform Has Small Entanglement
• Quantum metrology with a transmon qutrit
• Quantum codes for quantum simulation of Fermions on a square lattice of qubits
• A Deductive Verification Framework for Circuit-building Quantum Programs
• Simulating Many-Body Systems with a Projective Quantum Eigensolver
• Almost uniform sampling via quantum walks
• Adiabatic Quantum Simulators
• Effects of Dynamical Decoupling and Pulse-level Optimizations on IBM Quantum Computers
• A Variational Quantum Algorithm for Preparing Quantum Gibbs States
• Simulating quantum chemistry in the seniority-zero space on qubit-based quantum computers
• Faster Amplitude Estimation
• Quantum simulation of gauge theory via orbifold lattice
• Qubit-efficient encoding scheme for quantum simulations of electronic structure
• Collectively enhanced quantum measurements at the Heisenberg limit
• On low-depth algorithms for quantum phase estimation
• Reversible Circuit Optimization via Leaving the Boolean Domain
• Quantum Machine Learning in Drug Discovery: Applications in Academia and Pharmaceutical Industries
• Fast-forwarding quantum evolution
• A quantum gate array can be programmed to evaluate the expectation value of any operator
• Neural-network states for the classical simulation of quantum computing
• An efficient high dimensional quantum Schur transform
• Orbital transformations to reduce the 1-norm of the electronic structure Hamiltonian for quantum computing applications
• Level Reduction and the Quantum Threshold Theorem
• Efficient Quantum Algorithms for Shifted Quadratic Character Problems
• Heisenberg-limited quantum phase estimation of multiple eigenvalues with few control qubits
• Optimal compression of quantum many-body time evolution operators into brickwall circuits
• Adaptive Measurements in the Optical Quantum Information Laboratory
• Quantum-enhanced deliberation of learning agents using trapped ions
• Unitary Selective Coupled-Cluster Method
• A Stochastic Approach to Unitary Coupled Cluster
• A linearized stabilizer formalism for systems of finite dimension
• Quantum algorithms from fluctuation theorems: Thermal-state preparation
• The Quantum Fourier Transform and Extensions of the Abelian Hidden Subgroup Problem
• Resource estimate for quantum many-body ground-state preparation on a quantum computer
• A Universal Quantum Circuit Scheme For Finding Complex Eigenvalues
• Quantum walk based search algorithms
• Optimal measurements for the dihedral hidden subgroup problem
• Limits on Efficient Computation in the Physical World
• Projected Cooling Algorithm for Quantum Computation
• Sampling, rates, and reaction currents through reverse stochastic quantization on quantum computers
• Sparse Quantum State Preparation for Strongly Correlated Systems
• Complexity Classes of Equivalence Problems Revisited
• Spin-free quantum computational simulations and symmetry adapted states
• Towards an Automated Framework for Realizing Quantum Computing Solutions
• Faster quantum mixing for slowly evolving sequences of Markov chains
• Improved Accuracy for Trotter Simulations Using Chebyshev Interpolation
• Quantum conditional operations
• Quantum Monte Carlo for Economics: Stress Testing and Macroeconomic Deep Learning
• Efficient quantum imaginary time evolution by drifting real time evolution: an approach with low gate and measurement complexity
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Iterative phase estimation
• Multiscale Embedding for Quantum Computing
• An exponentially-growing family of universal quantum circuits
• Extending the Variational Quantum Eigensolver to Finite Temperatures
• Quantum algorithms for scientific computing
• Improved Bounds for Eigenpath Traversal
• Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
• Conditional Born machine for Monte Carlo event generation
• A unified framework of transformations based on the Jordan-Wigner transformation
• Quantum spectral clustering algorithm for unsupervised learning
• Neural network enhanced measurement efficiency for molecular groundstates
• Measurement-Based Time Evolution for Quantum Simulation of Fermionic Systems
• Discovering optimal fermion-qubit mappings through algorithmic enumeration
• Quantum Gaussian filter for exploring ground-state properties
• Low-depth simulations of fermionic systems on square-grid quantum hardware
• Sachdev-Ye-Kitaev circuits for braiding and charging Majorana zero modes
• Towards Large-Scale Quantum Computation
• Quantum Computing and Tensor Networks for Laminate Design: A Novel Approach to Stacking Sequence Retrieval
• Counterdiabatic optimized driving in quantum phase sensitive models
• Projective Cooling for the transverse Ising model
• Global Heisenberg scaling in noisy and practical phase estimation
• Simulating noisy quantum channels via quantum state preparation algorithms
• Molecular Structure Optimization based on Electrons-Nuclei Quantum Dynamics Computation
• Beyond MP2 initialization for unitary coupled cluster quantum circuits
• From Ansätze to Z-gates: a NASA View of Quantum Computing
• The Promise of Quantum Simulation
• Optimal Trace Distance and Fidelity Estimations for Pure Quantum States
• On proving the robustness of algorithms for early fault-tolerant quantum computers
• A Case for Synthesis of Recursive Quantum Unitary Programs
• Hückel Molecular Orbital Theory on a Quantum Computer: A Scalable System-Agnostic Variational Implementation with Compact Encoding
• Early Fault-Tolerant Quantum Algorithms in Practice: Application to Ground-State Energy Estimation
• Analytical formulation of the second-order derivative of energy for orbital-optimized variational quantum eigensolver: application to polarizability
• A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
• Dual-Frequency Quantum Phase Estimation Mitigates the Spectral Leakage of Quantum Algorithms
• Efficient Quantum Algorithms for the Hidden Subgroup Problem over a Class of Semi-direct Product Groups
• Quantum Complexity: restrictions on algorithms and architectures
• Foundations for Bayesian inference with engineered likelihood functions for robust amplitude estimation
• 1/f noise in quantum nanoscience
• Non-adiabatic Quantum Wavepacket Dynamics Simulation Based on Electronic Structure Calculations using the Variational Quantum Eigensolver
• A Classical Algorithm for Quantum $\text{SU}(2)$ Schur Sampling
• Tensor-based quantum phase difference estimation for large-scale demonstration
• Variational Quantum Algorithms for Differential Equations on a Noisy Quantum Computer
• Quantum Computation of Electronic Structure with Projector Augmented-Wave Method and Plane Wave Basis Set
• Projective Quantum Phase Difference Estimation Algorithm for the Direct Computation of Eigenenergy Gaps on a Quantum Computer
• Calculating the Green's function of two-site Fermionic Hubbard model in a photonic system
• Robust Preparation of Many-body Ground States in Jaynes-Cummings Lattices
• Flexibility of the factorized form of the unitary coupled cluster ansatz
• Energy risk analysis with Dynamic Amplitude Estimation and Piecewise Approximate Quantum Compiling
• The topology of data hides in quantum thermal states
• Electronic Structure in a Fixed Basis is QMA-complete
• A Quantum Implementation Model for Artificial Neural Networks
• Quantum Computing Applications for Flight Trajectory Optimization
• Quantum Pathways for Charged Track Finding in High-Energy Collisions
• On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems
• Nearly-frustration-free ground state preparation
• On Belief Propagation Decoding of Quantum Codes with Quaternary Reliability Statistics
• QuTracer: Mitigating Quantum Gate and Measurement Errors by Tracing Subsets of Qubits
• Reducing the Compilation Time of Quantum Circuits Using Pre-Compilation on the Gate Level
• Quantum Computing for Data Centric Engineering and Science
• Distinguishing n Hamiltonians on C^n by a single measurement
• Deterministic Algorithms for the Hidden Subgroup Problem
• Average-Case Verification of the Quantum Fourier Transform Enables Worst-Case Phase Estimation
• A comparison of three ways to measure time-dependent densities with quantum simulators
• Practical sampling schemes for quantum phase estimation
• Quantum Phase Estimation by Compressed Sensing
• Quantum collision circuit, quantum invariants and quantum phase estimation procedure for fluid dynamic lattice gas automata
• The 7 faces of quantum NP
• Quantum Spectral Clustering through a Biased Phase Estimation Algorithm
• Cryptography in a Quantum World
• Quantum Adjoint Convolutional Layers for Effective Data Representation
• Quantum Versus Classical Proofs and Advice
• Self-consistent Quantum Linear Response with a Polarizable Embedding environment
• Ladder Operator Block-Encoding
• Mixed-Dimensional Qudit State Preparation Using Edge-Weighted Decision Diagrams
• Quantum State Detection Via Elimination
• The Min-Entropy of Classical-Quantum Combs for Measurement-Based Applications
• Some Error Analysis for the Quantum Phase Estimation Algorithms
• Lower Bounds for Unitary Property Testing with Proofs and Advice
• Perfect Sampling for Quantum Gibbs States
• The Electronic Structure of the Hydrogen Molecule: A Tutorial Exercise in Classical and Quantum Computation
• Quantum Equivalence of the DLP and CDHP for Group Actions
• On solving systems of diagonal polynomial equations over finite fields
• Ground state energy and magnetization curve of a frustrated magnetic system from real-time evolution on a digital quantum processor
• Chemically Motivated Simulation Problems are Efficiently Solvable by a Quantum Computer
• Total Functions in QMA
• Constant-time Quantum Algorithm for Homology Detection in Closed Curves
• Photonic variational quantum eigensolver for NISQ-compatible quantum technology
• Topics in Estimation of Quantum Channels
• Convergence Rates for the Trotter Splitting for Unbounded Operators
• Does the full configuration interaction method based on quantum phase estimation with Trotter decomposition satisfy the size consistency condition?
• Multidimensional Electrical Networks and their Application to Exponential Speedups for Graph Problems
• An Improved Query for the Hidden Subgroup Problem
• Enhancing Scalability of Quantum Eigenvalue Transformation of Unitary Matrices for Ground State Preparation through Adaptive Finer Filtering
• On The Stabilizer Formalism And Its Generalization
• Quantum Computation and Communication in Bosonic Systems
• Efficient Construction of Functional Representations for Quantum Algorithms
• Ergodic quantum computing
• State of practice: evaluating GPU performance of state vector and tensor network methods
• Quantum counting, and a relevant sign
• Quantum Approximate Counting for Markov Chains and Application to Collision Counting
• Hybrid Quantum-Classical Clustering for Preparing a Prior Distribution of Eigenspectrum
• Sequential Bayesian experiment design for adaptive Ramsey sequence measurements
• Toward Density Functional Theory on Quantum Computers?
• Improved Quantum Query Complexity on Easier Inputs
• Generalization of Quantum Fourier Transformation
• Digital quantum simulation of strong correlation effects with iterative quantum phase estimation over the variational quantum eigensolver algorithm: ${\mathrm{H}}_4$ on a circle as a case study
• Quantum Multi-object Search Algorithm with the Availability of Partial Information
• Hybrid Path-Sums for Hybrid Quantum Programs