# Questions tagged [approximation]

The tag has no usage guidance.

10 questions
Filter by
Sorted by
Tagged with
279 views

### Is APPROX-QCIRCUIT-PROB a BQP-complete problem?

I've read contradictory information: on the Wikipedia page for BQP, it is written without proof that "APPROX-QCIRCUIT-PROB is a BQP-complete problem", while I have read elsewhere (don't ...
40 views

### Quantum compilation algorithm with respect to other Shatten $p$-norm

In standard quantum compilation algorithms (such as the Solovay-Kitaev theorem), one approximates an arbitrary unitary using words from some universal gate set. The "approximation" here is ...
89 views

### Bounding operator norm by total variation distance

Let $P_U(y \mid x) = |\langle y | U | x \rangle|^2$ denote the probability distribution of obtaining the bitstring $y \in \{0,1\}^n$ on a fixed input $x \in \{0,1\}^n$ w.r.t. the unitary $U$. For $n$-...
52 views

### Approximating the concatenation of two approximate circuits

Suppose I have two quantum circuits $A_n,B_n$ that I have already found to approximate the operations $U,V$ within some error $\epsilon_n$ and each with an overall circuit depth $\ell_n$ using $n$ ...
1 vote
392 views

### Clifford circuit approximation to a random Clifford circuit

Given a random Clifford state on $L$ qubits (defined as an infinite depth Clifford circuit acting on the zero state), what depth Clifford circuit is required to approximate this state to a given ...
1 vote
Suppose we are given Hamiltonian in the form: $$H = -\sum_{k=0}^{n-1} \alpha\sigma^x_k\sigma^x_{k+1} + \beta\sigma^y_k\sigma^y_{k+1} + \gamma\sigma^z_k\sigma^z_{k+1},$$ where $n$ is the number of ...