Skip to main content

Questions tagged [approximation]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
9 votes
2 answers
337 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 ...
Pierre Yves Schobbens's user avatar
3 votes
0 answers
56 views

Are there approximability schemes for NP-Hard problems using quantum algorithms? [duplicate]

I'm looking into some parts of Quantum Complexity Theory and was wondering if we have any approximability schemes for NP-Hard problems using quantum algorithms. I was unable to find any literature on ...
LukasM's user avatar
  • 53
3 votes
0 answers
66 views

Universal gate sets and conjugates of $SU(2)$

Let $G \subseteq SU(2)$ be a finite set, and let $E \in SU(2^k)$ be any entangling gate (so $k$ is some number strictly greater than 1). We often say $G$ is universal iff $\langle G \rangle$ is dense ...
trillianhaze's user avatar
2 votes
1 answer
83 views

Truncated Qumode States and Support

I am currently running numerical simulations of a single qumode state acted upon by a parameterised unitary. The qumode state is realised as a Fock state with a fixed cutoff dimension $(d)$ and is ...
Song of Physics's user avatar
2 votes
1 answer
48 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 ...
trillianhaze's user avatar
2 votes
1 answer
397 views

Calculation of Trotter-Suzuki error bound

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 ...
Albert65's user avatar
2 votes
1 answer
152 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$-...
trillianhaze's user avatar
2 votes
0 answers
56 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$ ...
User71942's user avatar
1 vote
1 answer
577 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 ...
as2457's user avatar
  • 330
1 vote
0 answers
82 views

Algorithm for finding the appropriate rotating frame Hamiltonian?

Context Consider an $N$-level Hamiltonian with energies $\omega_1...\omega_N$ with coupling drives at frequencies $f_{i,j}$ which couple the $i$ and $j$-th levels (not necessarily resonantly, so $f_{i,...
Dr. T. Q. Bit's user avatar
1 vote
0 answers
47 views

Improving operator norm bound on total variation distance

Let $U$ be an $n$-qubit unitary and $P_U(x) = |\langle x |U|0^n\rangle|$ the probability of measuring $x$ after acting $U$ on $|0^n\rangle$. For two $n$-qubit unitaries $U$ and $V$, one can prove that ...
trillianhaze's user avatar
1 vote
0 answers
57 views

Close in operator norm imply close in weak multiplicative sense?

Fix $\epsilon > 0$, and suppose $U$ and $S$ are $n$ qubit unitaries such that $\| U - S \| \leq \epsilon$ (operator norm). Furthermore, let $P_U(y \mid x) = |\langle y | U | x \rangle|^2$ be the ...
trillianhaze's user avatar
1 vote
0 answers
41 views

Error analysis on the approximation of an adiabatic evolution operator by a QAOA circuit

I would like to know what would be the approximation error of a QAOA circuit. Suppose we have time-dependent Hamiltonian $H(t) = (1 - s(t))H_{init} + s(t)H_{prob}$ where $H_{init}$ in an initial ...
MonteNero's user avatar
  • 2,908