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.

Filter by
Sorted by
Tagged with
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
3 votes
1 answer
92 views

Question about equivalence of two expressions for the Quantum Fourier transformation

The Quantum Fourier transformation on $n$ qubits is just the discrete Fourier transformation, $$ |j \rangle \mapsto \frac 1 {\sqrt 2^n}\sum_{k=0}^{2^n-1}e^{2\pi ijk/2^n}|k\rangle. $$ In binary ...
Konrad Waldorf's user avatar
3 votes
0 answers
105 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
2 votes
1 answer
140 views

Explain how to infer a density matrix from the statistics of quantum measurements

This question follows the "Probabilistic Simulation of Quantum Circuits with the Transformer" paper by Carrasquilla et al. In the Formalism section on page 2 the authors state that ...
Grwlf's user avatar
  • 135
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
1 answer
156 views

Approximations of the spectral radii of completely positive superoperators

Let $V$ be a finite dimensional complex Hilbert space. Let $L(V)$ denote the collection of all linear operators from $V$ to $V$. An operator $\mathcal{E}:L(V)\rightarrow L(V)$ is said to be positive ...
Joseph Van Name'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
34 votes
5 answers
4k views

What are the strongest arguments for a genuine quantum computing advantage?

Despite having become a fairly mature field with enormous sums of money dumped into research and development, there does not as yet exist a formal proof that quantum computation actually provides an ...
user6873235's user avatar
3 votes
0 answers
181 views

Normalizer of SU(2) x SU(2) in SU(4) [closed]

What is the normalizer of SU(2) x SU(2) in SU(4) or how would I find it? Reason for the question: with 2 qubits, if I was interested in conjugation of 2-qubit gates with generic SU(2) elements, ...
MarcoP's user avatar
  • 31
4 votes
1 answer
135 views

An introductory reference for tensor networks

I found a good reference on Tensor Networks: https://arxiv.org/abs/1912.10049. But I need an introductory reference with detailed proofs on Tensor Networks. Do you know another reference?
Aram's user avatar
  • 109
9 votes
0 answers
297 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
6 votes
1 answer
181 views

Applications of quantum representations of the mapping class group to quantum computers

Quantum representations of the mapping class group of a surface are certain representations constructed from the data of a TQFT and described, for example, in and 1 and 2. The following sources 3 ...
Yellow Pig's user avatar
  • 2,480
2 votes
1 answer
203 views

Is quantum turing machine equivalent classical turing machine? [closed]

I have the question if quantum computation is intrinsecally different to a classic computation. Thank you all!!
Camilo Argoty's user avatar
1 vote
1 answer
79 views

Complexity classes generated by differential equations

The quantum computer can be represented as a turing machine that sets up initial conditions for Schrodinger-like equation plus a fast ($O(1)$) solver for that equation. Is there a general study for ...
a user's user avatar
  • 111
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,806
5 votes
1 answer
809 views

What role do Hecke operators and ideal classes perform in "Quantum Money from Modular Forms?"

Cross-posted on QCSE An interesting application of the no-cloning theorem of quantum mechanics/quantum computing is embodied in so-called quantum money - qubits in theoretically unforgeable states. ...
Mark S's user avatar
  • 2,143
3 votes
0 answers
166 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
113 votes
11 answers
17k views

On mathematical arguments against Quantum computing

Quantum computing is a very active and rapidly expanding field of research. Many companies and research institutes are spending a lot on this futuristic and potentially game-changing technology. Some ...
1 vote
1 answer
294 views

How to create a quantum algorithm that produces 2 n-bit sequences with equal number of 1-bits?

I am interested in a quantum algorithm that has the following characteristics: output = 2n bits OR 2 sets of n bits (e.g. 2 x 3 bits) the number of 1-bits in the first set of n-bits must be equal to ...
JanVdA's user avatar
  • 121
0 votes
1 answer
301 views

QUBO formulation of a discrete-variable Genetic Algorithm optimization problem

I am facing a non-linear, discrete optimization problem, which I can formulate in this abstract manner: I have a certain non-analytic real-valued function $f$ depending on a set of parameters $ \theta\...
user116768's user avatar
13 votes
1 answer
1k views

Classification of unitary modular tensor categories (UMTCs)

Context/background: I'm approaching this topic from the perspective of anyonic systems. In the study of anyons, one works with fusion categories. Of course, for physicality, we demand that i) The ...
Sachin Valera's user avatar
5 votes
0 answers
285 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
11 votes
1 answer
320 views

Unique words in dihedral groups

Suppose $x$ is a word over the alphabet $\{0,1\}$. Let $a$, $b$ be elements of the group Dih$_k$ for some $k$. Let $\varphi=\varphi_{a,b,k}$ be the map from words over $\{0,1\}$ to elements of the ...
Bjørn Kjos-Hanssen'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
0 votes
1 answer
221 views

Is there a quantum Bayes rule?

This question has been bothering me for a while. Wading through the internet hasn't turned up any answers that I have been able to understand. First some motivation: Let $S = \{s_1,s_2,s_3\}$ be a ...
Daniel Barter's user avatar
8 votes
1 answer
379 views

Are there any unitary matrices which satisfy the Yang-Baxter equation which are universal for quantum computation?

Let $H$ be a finite dimensional hilbert space. Let $L:H\otimes H\rightarrow H\otimes H$ be a unitary transformation. Then the equation $$(L\otimes I)(I\otimes L)(L\otimes I)=(I\otimes L)(L\otimes I)(I\...
Joseph Van Name's user avatar
1 vote
1 answer
342 views

Fixed point of quantum operations

A quantum operation is defined as \begin{equation} \varepsilon(\rho)=\sum_{k}M_k\rho M_k^{\dagger} \end{equation} where $\varepsilon(\rho)$ takes an initial state $\rho$ to some final state $\rho'$ ...
Janus's user avatar
  • 35
13 votes
1 answer
11k 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 ...
Rhyzomatic's user avatar
14 votes
1 answer
3k 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 ...
Craig Feinstein's user avatar
3 votes
1 answer
302 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) ...
Māris Ozols's user avatar
11 votes
1 answer
665 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 ...
John Sidles's user avatar
  • 1,359
8 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
935 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 ...
Gina Martelli's user avatar
13 votes
2 answers
1k 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 ...
Řídící's user avatar
13 votes
4 answers
2k 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 ...
Dustin G. Mixon's user avatar
14 votes
3 answers
3k 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 ...
Joël's user avatar
  • 25.7k
2 votes
2 answers
665 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 ...
Eunou's user avatar
  • 21
11 votes
1 answer
4k 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 ...
Mirco A. Mannucci's user avatar
5 votes
1 answer
312 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 ...
André Henriques's user avatar
7 votes
6 answers
3k 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 =...
Ross Duncan's user avatar
3 votes
1 answer
1k 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\}$ and ...
Jess Riedel's user avatar
4 votes
1 answer
559 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 (...
Vanessa's user avatar
  • 1,358
0 votes
2 answers
617 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) ...
Alex 'qubeat''s user avatar
6 votes
1 answer
335 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 ...
Tracy Hall's user avatar
  • 2,140
3 votes
0 answers
750 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
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 ...
Noah Rahman's user avatar
7 votes
3 answers
2k 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 ...
Steven Landsburg's user avatar
0 votes
1 answer
1k 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 ...
Shishir Pandey's user avatar
3 votes
2 answers
1k 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 ...
Steve Huntsman's user avatar