Two constructions yield strong unitary k-designs and pseudorandom unitaries on D-dimensional grids with provably optimal depth.
Approximation by quantum circuits.arXiv preprint quant-ph/9508006
5 Pith papers cite this work. Polarity classification is still indexing.
5
Pith papers citing it
abstract
In a recent preprint by Deutsch et al. [1995] the authors suggest the possibility of polynomial approximability of arbitrary unitary operations on $n$ qubits by 2-qubit unitary operations. We address that comment by proving strong lower bounds on the approximation capabilities of g-qubit unitary operations for fixed g. We consider approximation of unitary operations on subspaces as well as approximation of states and of density matrices by quantum circuits in several natural metrics. The ability of quantum circuits to probabilistically solve decision problem and guess checkable functions is discussed. We also address exact unitary representation by reducing the upper bound by a factor of n^2 and by formalizing the argument given by Barenco et al. [1995] for the lower bound. The overall conclusion is that almost all problems are hard to solve with quantum circuits.
citation-role summary
background 1
citation-polarity summary
fields
quant-ph 5roles
background 1polarities
background 1representative citing papers
Two enhancements to the Grover-Rudolph algorithm reduce CNOT gates and control qubits for sparse quantum state preparation, including an approximate variant with a classically computable overlap estimate.
Reformulation of Cartan-Khaneja-Glaser decomposition for SU(2^n) via involutive automorphisms and symmetric Lie algebra decompositions yields a stable recursive factorization with open-source Python code validated on SU(8) and SU(16).
A quantum Monte Carlo algorithm solves multidimensional Black-Scholes PDEs for option pricing with polynomial complexity in dimension d and accuracy 1/ε, with rigorous error bounds and a claimed speedup over classical Monte Carlo for bounded payoffs.
Computational complexity of random multi-qudit states and unitaries scales exponentially with qudit number, while physical complexity scales more slowly.
citing papers explorer
-
Arts & crafts: Strong random unitaries and geometric locality
Two constructions yield strong unitary k-designs and pseudorandom unitaries on D-dimensional grids with provably optimal depth.
-
Approximate Sparse State Preparation with the Grover-Rudolph Algorithm
Two enhancements to the Grover-Rudolph algorithm reduce CNOT gates and control qubits for sparse quantum state preparation, including an approximate variant with a classically computable overlap estimate.
-
Cartan-Khaneja-Glaser decomposition of $SU(2^n)$ via involutive automorphisms
Reformulation of Cartan-Khaneja-Glaser decomposition for SU(2^n) via involutive automorphisms and symmetric Lie algebra decompositions yields a stable recursive factorization with open-source Python code validated on SU(8) and SU(16).
-
Quantum Monte Carlo algorithm for option pricing and its complexity analysis
A quantum Monte Carlo algorithm solves multidimensional Black-Scholes PDEs for option pricing with polynomial complexity in dimension d and accuracy 1/ε, with rigorous error bounds and a claimed speedup over classical Monte Carlo for bounded payoffs.
-
Computational and physical complexity of synthesizing random multi-qudit quantum states and unitary operators
Computational complexity of random multi-qudit states and unitaries scales exponentially with qudit number, while physical complexity scales more slowly.