The quantum-computation tag has no usage guidance.

**0**

votes

**0**answers

17 views

### If BQP is contained in any level of the Polynomial Hierarchy, does it then follow that $NP \subseteq BQP$ implies $PH \subseteq BQP$? [migrated]

I think this is implied in this paper by Aaronson (http://www.scottaaronson.com/papers/bqpph.pdf) but I am not sure.

**4**

votes

**1**answer

278 views

### Constructing the oracle for Grover's algorithm

For a final project in my class, I decided to try to simulate a quantum computer and implement Grover's algorithm. I followed this excellently written blog post by Craig Gidney, and was successful in ...

**11**

votes

**1**answer

503 views

### Can Shor's Algorithm be modified to run efficiently on a classical computer?

Shor's algorithm is an algorithm which factors integers in polynomial time on a quantum computer. If one tries to run it on a classical computer, one runs into the problem that the state vector that ...

**2**

votes

**1**answer

220 views

### Why a tensor product of $2\times 2$ unitaries cannot implement a $3\times 3$ unitary?

Let $\{v_1, \dotsc, v_m\} \in \mathbb{C}^{2^n}$ be a set of orthonormal vectors. Define a map $R_m$ from $2^n \times 2^n$ to $m \times m$ matrices as follows:
$$R_m(M) := \sum_{i,j=1}^m (v_i^*M v_j) ...

**10**

votes

**1**answer

403 views

### Do quantum “Sure-Shor separators” have a natural Veronese/Segre classification? (question inspired by Gil Kalai and Aram Harrow)

Aram Harrow asked: "Is there any place this is written up?"
Update Partly in answer to Aram's question, the thermodynamical properties of varietal dynamical systems now are written-up in ...

**7**

votes

**1**answer

1k views

### What is the “Tangle” at the Heart of Quantum Simulation?

The following questions generalize and naturalize the question that was originally asked. Provisional answers largely due to Will Sawin are now included.
As was discussed in the question originally ...

**12**

votes

**3**answers

619 views

### Representing SU(3) with 3 ropes in 3 dimensions

The short question is: how exactly is SU(3) realized with ropes?
The long question: There is this idea that deformations of a configuration of three infinitely long, flexible ropes that cross each ...

**11**

votes

**2**answers

684 views

### Is quantum game theory reducible to classical game theory?

Quantum game theory is an extension of classical game theory to the quantum domain. It differs from classical game theory in three primary ways:
Superposed initial states,
Quantum ...

**10**

votes

**4**answers

1k views

### Quantum algorithms for dummies

I want to try my hand at designing quantum algorithms to solve certain problems. I feel like I understand (for example) how Grover's algorithm and Shor's algorithm work, and I'm excited to apply the ...

**12**

votes

**3**answers

2k views

### Will quantum computing kill cryptography ? [closed]

I apologize as this question is not really mathematical, and therefore perhaps not
well-suited for this site. Please feel free to close it if you think it is not. My reason
for asking it here is that ...

**2**

votes

**2**answers

219 views

### How can I get all the good items using quantum search algorithm?

One can get a superposition of all good item using quantum search algorithm in $O$($\sqrt{N}$ ) time, but how one can get all the good items using quantum search algorithm?
I found that all the good ...

**6**

votes

**1**answer

900 views

### How much does a quantum oracle to find a needle in a haystack really cost?

Among the basic algorithms of quantum computations Lov Grover's result on quantum search stands out, both in regards to its intrinsic interest, and for its undisputable elegance.
Grover's algorithm ...

**5**

votes

**1**answer

278 views

### Set of physical states of FQHE on closed Riemann surface = ?

Disclaimer. One might argue that my question is off topic as it is clearly a question about physics... But I'd like a mathematically phrased answer,
and I expect that only a mathematician can offer an ...

**2**

votes

**5**answers

864 views

### Presentation of the Clifford group by generators and relations?

The Clifford group $\mathcal{C}_n$ is a matrix group on $\mathbb{C}^{2^n}$ generated by tensor products of the following matrices:
$$
P = \begin{pmatrix} 1 & 0 \\\\ 0 & i\end{pmatrix}
\quad
H ...

**2**

votes

**1**answer

684 views

### Bounding the von Neumann entropy of a density matrix with the Hilbert-Schmidt norm

Question
Suppose I have a $D$-dimensional density matrix $\rho_0$
$\rho_0^\dagger = \rho_0 \quad, \quad \mathrm{Tr} \rho_0 = 1 \quad, \quad \rho_0 > 0,$
with a known spectrum $\{\lambda_i^0\}$ ...

**3**

votes

**1**answer

426 views

### Are all quantum cellular automata invertible & representable?

A little background: As far as I know there is no standard definition of a quantum cellular automaton in the literature. Different authors use different definitions. Here I propose my own definition ...

**0**

votes

**2**answers

449 views

### A non-associative three-valued logic

There are three elements: x, y, z and a relation C:
x C y, y C z, z C x, x C x, y C y, z C z.
Let us introduce two binary operations with respect to the C: "the leftmost" (L) and "the rightmost" ...

**5**

votes

**1**answer

277 views

### Standard reference for equivalence of PU(2) action on $\mathbb{C}\mathbb{P}^1$ and SO(3) action on $S^2$

The equivalence I describe below is well-known, but I'd like a simple standard reference for it.
Consider $\mathbb{C}\mathbb{P}^1$, the set of one-dimensional subspaces of $\mathbb{C}^2$, which has a ...

**3**

votes

**0**answers

645 views

### Why isn't Montgomery modular exponentiation considered for use in quantum factoring?

It is well known that modular exponentiation (the main part of an RSA operation) is computationally expensive, and as far as I understand things the technique of Montgomery modular exponentiation is ...

**9**

votes

**2**answers

2k views

### Quantum PCP Theorem

Although I think I know the answers to these, I'd just like to collect them all in one place.
What is the quantum PCP theorem, what implications does its proof have for simulation of Hamiltonians and ...

**7**

votes

**3**answers

1k views

### Grover's Quantum Search Algorithm

I am confused about an extremely basic point concerning Grover's quantum search algorithm; my confusion suggests to me that maybe I've missed the entire point.
My understanding of the algorithm is ...

**0**

votes

**1**answer

385 views

### Linear Mapping and integration

I have been reading the paper - "Introduction to Quantum Fisher Information".
In section 1.2 the author talks about the linear map $\mathbb{J}_D$, which he defines as follows:
Let $D \in M_n$ be a ...

**3**

votes

**2**answers

824 views

### Amplitude amplification as a quantum walk algorithm

This is a followup to an earlier question on a taxonomy for quantum algorithms in which I ultimately concluded in a comment that all known nontrivial quantum algorithm speedups (in Jordan's quantum ...

**7**

votes

**2**answers

500 views

### What's known about the relationship about EQP and BQP?

EQP is the class of problems solvable deterministically using a quantum computer in polynomial time - that seems to me to be a good analogue to P, whereas BQP is the quantum analogue of BPP.
It ...

**10**

votes

**2**answers

899 views

### Are there any known quantum algorithms that clearly fall outside a few narrow classes?

I'm trying to refresh myself on quantum algorithms and have been skimming Childs and van Dam's 2008 RMP paper among other things. From my preliminary surfing it looks like the known quantum algorithms ...