The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
12 views

Complexity Theory

Let x ∈ {0, 1}$^{n}$ have disjoint sensitive blocks $S _{1} , . . . S _{bs(f )}$ . For any y ∈ {0, 1}$^{bs(f )}$ , let x$^{[y]}$ denote x with x$_{i}$ replaced by $\bar x_{i}$ if i ∈ S$_{j}$ and y + j ...
0
votes
0answers
38 views

Grover's algorithm

Any help is appreciated! I've read over a bunch of sources but still I don't get the question. Consider a function $f \colon \{0,1\}^n\to\{0,1\}$ such that the number of $x\in\{0,1\}^n$ such that ...
0
votes
1answer
17 views

Toffoli gates can be decomposed into single and two-qubit gates

I'm not sure what the "I" and "-I" gates do. I can't seem to apply them correctly. When I do hadimard I get |00>(Tensor)Hadimard. If I then apply the tensor product to apply the 'i' gate on the last ...
0
votes
0answers
9 views

How to represent controlled quantum circuits as matrices?

I'm trying to implement (actually, simulate) the quantum algorithm by Harrow, Hassidim and Lloyd - http://arxiv.org/abs/0811.3171 - to solve linear systems of equations using a simple $2\times2$ case ...
3
votes
1answer
45 views

Notation in formula for tensor product of Hadamard matrix

I'm having trouble understanding the notation used in a linear algebra exercise (it's exercise 2.33 of Nielsen and Chuang's "Quantum Computation and Quantum Information", page 74). The exercise gives ...
3
votes
0answers
61 views

Understanding the Quantum Fourier Transform

I have a question about the Quantum Fourier Transform. I would like to understand it because I have a re-take for an exam. I have studied the provided / recommended literature extensively. ...
1
vote
1answer
33 views

Specific system of equations with multiplications

I'm facing a math problem that I thought easy, but I'm stuck with a solution that doesn't seem optimal. The problem is the following : I have "registers" which are the expanded representation of ...
2
votes
1answer
34 views

Promise of the hidden subgroup problem for $\mathbb{Z} mod 2$

I am going through the talk, Graph isomorphism, the hidden subgroup problem and identifying quantum states, by Pranab Sen. On slide 3, the promise of the problem is defined as follows. Here is the ...
3
votes
1answer
41 views

Hidden subgroup problem for $\mathbb{Z} mod 2$

The definition of the Hidden Subgroup Problem (HSP) is as follows (according to a lecture series by Pranab Sen), Let $G$ be a group, $S$ a set and $f : G \to S$ a function. We are given an ...
4
votes
0answers
48 views

Standard deviation of a quantum walk?

The standard deviation of a classical random walk with $n$ steps is $\sqrt n$ - Standard deviation of a random walk. I have read in many places that the standard deviation of a quantum walk $n$ with a ...
1
vote
0answers
41 views

In the Stinespring dilation theorem, what is the minimum dimension for which a dilation Hilbert space of this form is guaranteed to exist?

This may look like a problem that could easily be looked up, but it's not quite as easy as it first appears, hence my asking. I'm going to phrase my question in terms of the "Schroedinger picture" ...
1
vote
1answer
44 views

Quantum: Toffoli gates

How do I prove that a toffoli gate is a controlled CNOT gate. i.e, $G_{Toffoli} = |0\rangle\langle 0| \otimes I + |1\rangle\langle 1|\otimes G_{CNOT}$. I am not sure how to approach this, thoughts? ...
0
votes
0answers
17 views

relationship between the CNOT gate and the I and X single-qubit gates

I need to prove this relationship: $G_{CNOT} = |0\rangle\langle 0| \otimes I + |1\rangle\langle 1|\otimes X$. So I think I need to show that both sides are a linear map on $H \otimes H \otimes H$ So ...
0
votes
0answers
33 views

Bounding parameters for Shor's Algorithm

I am working on a program for classical implementation of Shor's algorithm to factor products of small primes, just to better understand how it works. The program will conduct order finding using ...
2
votes
1answer
93 views

Rotation of the Bloch Sphere

I was reading through the book "Quantum Computation and Quantum Information for Computer Scientists", and I got up to a problem about rotation matrices on the block sphere and I can't figure it out at ...
1
vote
0answers
50 views

a quantum algorithm with high probability on a 4 to 1 function

Let $f : $ {0,1}$^n \rightarrow $ {0,1}$^n$ be a 4-to-1 function, such that there exist distinct and non-zero $a,b\in $ {0,1}$^n$ such that for all $x\in$ {0,1}$^n$: $f(x) = f(x ⊕ a) = f(x ⊕ b) = ...
1
vote
2answers
30 views

Hermitian - Using the Spectral Theorem

Ok so I am trying to show that if A is normal and has real eigenvalues, then A is hermitian. It was suggested that I try using the spectral theorem. So if we assume A is normal and has real ...
0
votes
1answer
83 views

Quantum Computing - Conjugate Transpose and Tensor Products

Show that $(A^T)^T = A$, where T is the conjugate transpose of the matrix. $$\left|\psi\right\rangle = \alpha_0\left|0\right\rangle + \alpha_1\left|1\right\rangle\; ...
1
vote
1answer
40 views

Conveity of quantum Fisher information

Let R be any quantum state and X any observable, then we define F(R,X)=4Tr(L^2 . R) as the quantum Fisher information. Where L is the logarithmic derivative determined by i(R.X - X.R)=(L.R + R.L)/2 I ...
2
votes
1answer
30 views

Continous and Discrete basis, Multiplication of Density Matrix and Hamiltonian.

Suppose I have a wave function $\psi(x)$ in position basis. I can make a density function by simply multiplying $\psi(x)$ and its conjugate $\psi^*(x)$. If I operate the density matrix ...
5
votes
1answer
56 views

Defining conditional quantum probability

My knowledge of quantum mechanics is very limited, but I will try to ask a purely mathematical question here. If there is a text or resource that explains this, I would definitely appreciate any ...
1
vote
0answers
47 views

If P = NP can asymmetric key exchanges still exist?

One functions are easy to compute (ie polynomial time checking) but hard to reverse. if P = NP does that mean that asymmetric key exchanges will be reduced from polynomial computation time and ...
0
votes
1answer
26 views

Special Quantum Gate

Given $\alpha|1\rangle+\beta|0\rangle$, to transform to $|\phi\rangle=\alpha|0\rangle+\beta|1\rangle$ , we use Quantum NOT gate: NOT = $\begin{pmatrix}0 & 1 \\ 1 & 0\end{pmatrix}$. For ...
0
votes
1answer
35 views

Pauli Spin Operator General Rotation

I would like to calculate the Pauli spin operator rotation $$ U^{\dagger } \overset{\rightharpoonup }{\sigma } U$$ where $$\overset{\rightharpoonup }{\sigma }=\sigma _x \overset{\rightharpoonup ...
1
vote
1answer
41 views

Probability distribution of two party quantum states

I am going through a blog post written by Thomas Vidick. It states following three assumptions by Bell. Measurement independence (“free will”): the state $\lambda$ is independent of ${x,y}$ (since ...
1
vote
1answer
127 views

Simon's algorithm for n = 3

The Simon's problem is as follows: Suppose we are given a function $f : \{0, 1\}^n \to \{0, 1\}^m$, with $m \ge n$, and we are promised that either $f$ is 1-to-1, or there exists a non-trivial s such ...
1
vote
1answer
63 views

Fourier transformations in Simon's quantum paper

I am reading this paper by Simon. This is one of the earliest quantum algorithm papers. In the paper he presents a routine starting at the end of page six. The first step runs a Fourier transformation ...
2
votes
0answers
101 views

Quadratic Diophantine Equations in Polynomial Time

Considering the problem of finding lattice points $(x_1, x_2 ... x_n)$ that satisfy a quadratic law: $F(x_1, x_2... x_n) = 0$ such that $F(x_1, x_2... x_n)$ is a second degree polynomial It is ...
2
votes
1answer
152 views

Unit Matrices for $M_n(M_n(\mathbb{R}))$

In the case of $M_n(\mathbb{R})$ we can define unit matrices $E_{ij}$ in the following way, $$E_{ij}f_l = \delta_{lj}f_i$$ where the $\{f_i\}$ is a basis for our space. One consequence of this ...
1
vote
0answers
145 views

How to Diagonalize an Extremely Large Sparse Matrix in SLEPc/PETSc

Dear Friends, Recently I have started with learning SLEPc/PETSc, but I didn't find a way to solve my problem. I have to solve a big sparse matrix which is a two dimensional quantum ...
1
vote
1answer
77 views

Dense in the special unitary group

I was going through the PhD thesis of Daniel Nagaj. In the last paragraph on page 30, there is this following sentence. A universal gate set must be dense in the group $SU(n)\ldots$ My question ...
2
votes
0answers
293 views

Is quantum game theory reducible to classical game theory? [closed]

Modnote: This question was manually migrated (closed and crossposted) to MathOverflow by request of the OP. Quantum game theory is an extension of classical game theory to the quantum domain. It ...
6
votes
2answers
419 views

Is a bra the adjoint of a ket?

The instructor in my quantum computation course sometimes uses the equivalence $$(\left|a\right>)^\dagger\equiv\left<a\right|$$ I understand that this is true for the typical matrix ...
2
votes
1answer
355 views

Does bra-ket notation work for all inner product spaces?

My quantum computation instructor keeps referring to the vector space in which he is using Dirac's bra-ket notation as an "inner product space", but doesn't it need additional properties to use that ...
2
votes
1answer
69 views

Factoring of exponents in Simon's algorithm

In derivations of Simon's algorithm (e.g., p. 4), it's often meant to be apparent that $$(x_0\oplus s)\cdot y=(x_0\cdot y)+(s\cdot y)$$ where $\oplus$ is "direct sum modulo 2", $x_0,s,y$ are all ...
5
votes
1answer
107 views

Quantum Information: Deutsch-Jozsa Algorithm

There is a step in the construction of this algorithm which I'm not understanding: $\displaystyle \left[\sum_x \frac{| x \rangle}{\sqrt{2^n}}\right]\left[\frac{ | 0 \rangle -| 1 \rangle ...