Questions tagged [quantum-computation]
Quantum computing is a model of computation that uses quantum bits instead of classical $0/1$ bits. This allows for the superposition of classically allowable states. Relevant topics include quantum algorithms (e.g. Shor's factoring algorithm), quantum information theory, quantum entanglement, and quantum annealing.
11
questions with no upvoted or accepted answers
9
votes
0
answers
302
views
The geometry of lambda calculus?
I stumbled upon "the geometry of quantum computation" --- to quote the abstract:
Determining the quantum circuit complexity of a unitary operation is closely related to the problem of finding ...
5
votes
0
answers
286
views
Quantum P vs NP equivalent problem
If $P = NP$, does it follow that $BQP = NP^{BQP}$?
I came up with this question when I was thinking about how $P = NP$ can be described as "does every decision problem where a proof for YES can be ...
3
votes
0
answers
106
views
Could a quantum computer factor $N=p\times q$ using Hadamard transforms on $x^2\bmod N$ (instead of Fourier transforms on $a^x\bmod N$)?
In Classically verifiable quantum advantage from a computational Bell test, Kahanamoku-Meyer, Choi, Vazirani, and Yao propose using $x^2 \bmod N$ in an interactive proof-of-quantumness. This is a two-...
3
votes
0
answers
128
views
determine degree of boolean polynomial given as black box
I searched a lot but couldn't find a good resource that addresses this question. Given a boolean polynomial with $n$ boolean variables as a black box, what is the most efficient way to compute its ...
3
votes
0
answers
75
views
Functional characterization of local correlation matrices?
Definition: A matrix $C\in\mathbb R^{m\times n}$ is local correlation matrix iff there exists real random variables $x_1,\dots,x_m,y_1,\dots,y_n$ defined on a common probability space which takes ...
3
votes
0
answers
169
views
Efficient implementation of the Clifford group for $n$ qubits
I'm looking for an efficient implementation of the Clifford group $\mathcal{C}_n$
of $n$ qubits.
The Clifford group $\mathcal{C}_n$ has stucture $(2_+^{1+2n} \circ C_8).Sp(2,n)$,
where $2_+^{1+2n}$ ...
3
votes
0
answers
71
views
Multilinear maps that preserve unitarity
Let $M_1, M_2, M_3$ be spaces of square complex matrices, respectively acting on finite-dimensional Hilbert spaces $V_1, V_2$, and $V_3 = V_1 \otimes V_2$. Consider bilinear maps
$$\phi: M_1 \times ...
3
votes
0
answers
751
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 ...
1
vote
0
answers
29
views
Is every nearly rank 1 doubly stochastic superoperator the product of pairwise averagings of unitary channels?
Suppose that $\mathcal{X}$ is a finite dimensional complex Hilbert space. Let $L(\mathcal{X})$ denote the collection of all linear mappings from $\mathcal{X}$ to $\mathcal{X}$. We say that a linear ...
0
votes
0
answers
24
views
Estimating ground state energy of $n$-qubit $2$-local Hamiltonian $H$ with known coefficients
Suppose we have an $n$-qubit $2$-local Hamiltonian $H$ with known coefficients. The eigenvalues of $H$ lie in $[0,1)$ and can all be written exactly with $[2 \log_2n]$ bits of precision. You would ...
0
votes
0
answers
60
views
Is there a normal form for completely positive superoperators with rotationally symmetric spectra?
Let $d$ be a natural number. Given $A_1,\dots,A_r\in M_d(\mathbb{C})$, define a linear operator
$\Phi(A_1,\dots,A_r):M_d(\mathbb{C})\rightarrow M_d(\mathbb{C})$ by letting
$\Phi(A_1,\dots,A_r)(X)=...