Almost-Optimal Computational Basis State Transpositions

2023/09/22 by Herbert, Steven, Sorci, Julien, Tang, Yao · 3 citations
#FOS: Physical sciences #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.2309.12820

Abstract

We give an explicit construction to perform any n-qubit computational basis state transposition using Θ(n) gates. This nearly coincides with the lower bound Ω(n/log(nd)) on worst-case and average-case gate complexity to perform transpositions using a d-element gate-set, which we also prove.

Cited by

• Realization of a Quantum Streaming Algorithm on Long-lived Trapped-ion Qubits
• Quantum Search in Superposed Quantum Lattice Gas Automata and Lattice Boltzmann Systems
• Fully Quantum Lattice Gas Automata Building Blocks for Computational Basis State Encodings

Related

• Construction of the Complete Set of Maximally Entangled Basis Vectors for N-Qubit Systems
• A Framework for Approximating Qubit Unitaries
• Halving the cost of quantum multiplexed rotations
• Best Approximate Quantum Compiling Problems
• Transversal gates for probabilistic implementation of multi-qubit Pauli rotations