# Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

356 questions
Filter by
Sorted by
Tagged with
270 views

### Generating quadratic optimization problems amenable to quantum annealing

Some context: there is a current debate in adiabatic quantum computing over whether a particular machine, the D-Wave quantum annealer, can outperform a classical algorithm [*]. Earlier this year, a ...
307 views

937 views

### $\ell_p$-norm preserving Turing machines

Reading some recent threads on quantum computing (here,here, and here), make me remember an interesting question about the power of some kind of $\ell_p$-norm preserving machine. For people working ...
1k views

### Computation beyond unitary matrices

Just out of curiosity, if the classical computation is about permutation matrices and quantum computing is about unitary matrices (of which the permutation matrices are a subgroup), then will there be ...
268 views

### Running Simon's algorithm on D-wave machine

I was wondering whether Simon's algorithm could be run on a D-wave machine. The Simon's algorithm is a promise problem. On the other hand the D-wave machine can run only quadratic unconstrained ...
197 views

### How hard it is to approximate the ground state of the (2-D) Hubbard model

The Hubbard model (see also the wikipedea article on the Bose-Hubbard model) is a basic quantum model of solid-state physics. Question: What is the computational complexity of approximating the ...
169 views

### Are NQP and QMA comparable?

Both definitions try to create a quantum analog for NP. NQP's definition comes from non-deterministic algorithms: it contains languages for which a Quantum Algorithm accepts with non-zero probability ...
157 views

### Why is Shor's algorithm in $BPP^{BQNC}$ when needing to uncompute subprocedure call?

Why is Shor's algorithm in $BPP^{BQNC}$? It's true the quantum Fourier transform is in $BPP^{BQNC}$, but the algorithm needs to call a number theoretic function f which has period p which is a factor ...
124 views

### Determining if a function is constant or not using period finding

Consider an arbitrary boolean function $$f: {\lbrace 0,1 \rbrace}^n \rightarrow \lbrace 0,1 \rbrace$$ which we write as: $$f(x_1, x_2 ... x_n)$$ where each $x_i$ is a boolean variable We note ...
464 views

### Sampling satisfiable 3-SAT formulas

Consider the following computational task: We want to sample a 3-SAT formula of $n$ variables (a variant: $n$ variables $m$ clauses) with respect to the uniform probability distribution, conditioned ...
128 views