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
Filter by
Sorted by
Tagged with
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 ...
Siddharth Bhat's user avatar
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 ...
NXTangl's user avatar
  • 51
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-...
Mark S's user avatar
  • 2,143
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 ...
Math-fort's user avatar
  • 103
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 ...
VS.'s user avatar
  • 1,816
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}$ ...
Martin Seysen's user avatar
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 ...
philippe's user avatar
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 ...
Steve Huntsman's user avatar
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 ...
Joseph Van Name's user avatar
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 ...
QiFeng233's user avatar
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)=...
Joseph Van Name's user avatar