Quantum computation and computational issues related to quantum mechanics

learn more… | top users | synonyms (1)

0
votes
0answers
3 views

Are parts of the Quantum ZX Calculus impossible in real circuits?

The ZX calculus is a calculus for reasoning about Quantum systems. A rather intuitive tutorial is found here. In the ZX calculus certain nodes do not have equal numbers of inputs and outputs. For ...
-1
votes
1answer
26 views

How are new probabilities computed when simulating measurement on a set of qubits?

Suppose I have a set of 3 qubits and I have the probabilities for their distribution. This could be arbitrarily entangled or pure: |000> -> a |001> -> b |010> -> c |011> -> d |100> -> e |101> -> f |...
-1
votes
0answers
27 views

How to interpret these adiabatic evolutions?

I was trying to study the adiabatic Hamiltonian defined in the paper (arXiv:1207.1712) titled 'Solving the Graph Isomorphism Problem with a Quantum Annealer'. My case is the cycle graph $C_n$ when $n$...
6
votes
1answer
515 views

States and Probability distributions that the 5-qubits IBM computer can produce

IBM has recently built a 5-qubits quantum computers based on superconducting qubits. It is even possible to make experiments over the cloud. The space of pure states for 5 qubits is the unit sphere ...
-3
votes
0answers
20 views

Can Quantum Computing solve Problems not even a Turing Maschine can solve? [migrated]

In his book "The Fabric of Reality", Penguin Books 1998, p. 218, David Deutsch says that the first quantum computer (built 1989 in the office of Charles Bennet, IBM Reasearch) "became the first ...
0
votes
0answers
43 views

How do I figure out how to combine simpler quantum gates to create the gate I want?

I want to create other quantum gates from the basic building blocks of a universal quantum gate set. I've been playing with IBM's quantum computing interface for that. I wanted to create a Toffoli ...
1
vote
1answer
45 views

Can a measurement commuting with the stabilizer of a state disturb the state?

In Nielsen and Chuang's "Quantum Computation and Quantum Information", Section 10.5.3, the authors claim the following: With a system in state $|\psi\rangle$ with stabilizer $g_1,...,g_n$, if a ...
3
votes
1answer
138 views

theorems for universal set of quantum gates for SU(d)

It seems that there is a theorem that for prime dimension d, the set of Clifford gates and one non-Clifford gate together forms a universal set of quantum gates for SU(d). It also seems that for a ...
4
votes
1answer
54 views

Is it possible to MAC a quantum state with a classical key under reasonable assumption?

Assume that classical one-way functions secure against quantum adversaries exist. Is it possible, given a quantum state $Q$ and classical secret key $k$, produce a quantum state $AuthQ$ such that: ...
2
votes
1answer
78 views

Is it possible to encrypt quantum states under reasonable assumptions?

Is it possible to encrypt a quantum state, such that a $BQP$ attacker who does not know the secret key cannot obtain any information about the original state, but a $BQP$ decryptor with the key can ...
11
votes
1answer
162 views

Is there a survey of the field of quantum automata?

I'm looking for a survey paper of the important concepts in the field of Quantum Automata. I've found Quantum Automata Theory -- A Review by Hirvensalo, but it sounds too succinct to grasp the topic. ...
0
votes
0answers
68 views

In the algorithm of quantum phase estimation, how the deviation of unitary operation affect the result of obtained phase?

Given an unitary operation $U$ and one of its eigenvector state $|u\rangle$ such that $U|u\rangle=e^{2\pi i \phi}|u\rangle$, the algorithm of quantum phase estimation can be utilized to estimate the ...
2
votes
2answers
287 views

Quantum complexity of maximum inner product search

Given two matrices $X \in \mathbb{R}^{m \times k}$, $Y \in \mathbb{R}^{n \times k}$, maximum inner product search (MIPS) asks for the largest $l$ entries of $X Y^T$. Typically $k \ll m, n$ (many ...
0
votes
0answers
72 views

Quantum Data Compression Schemes

Quantum Computation has given speedups in algorithms, and even though we do not know the exact relationship of $BQP$ to $NP$ -we have many algorithms in quantum computation that give speedup in ...
1
vote
0answers
68 views

Quantum algorithms for generalizations of determinants

There are a wide variety of determent-like constructions. Some like the permanent or immanents are variations on the ordinary determinant for matrices over fields or commutative rings. Some like ...
3
votes
0answers
80 views

On FFT and trigonometric matrix eigenvalues

Let $N=2^n$ for a natural number $n$ and $B$ be the $N\times N$ square matrix of $0$'s and $1$'s $$ B=\begin{pmatrix} 0 & 1 & 0 & \ldots & 0 \\ 1 & 0 & 1 & \ldots ...
1
vote
0answers
116 views

Quantum computer versus Random 3-SAT?

It seems to be commonly believed that quantum computer cannot efficiently solve NP-hard problems. What about the challenging problems in average-case, such as Planted Clique and Random 3-SAT?
3
votes
0answers
80 views

Quantum GCD circuit: On reversibility and clearing ancillae

Originally posted on PHYS, however, obviously it has more to do with CS I am currently trying to implement a circuit for computing the greatest common divisor in the Quantum Computing Language. In my ...
1
vote
1answer
53 views

Is unbounded quantum fanout operation experimentally feasible?

It is known that the "unbounded quantum fanout operation" is very powerful: (See, for example, Hoyer et al. : http://theoryofcomputing.org/articles/v001a005/v001a005.pdf). In particular, it is known ...
1
vote
1answer
47 views

How the hardness of hidden subgroup problem in $S_n$ changes as the order of the subgroup grows?

In Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al. In this paper it is showed that no hidden subgroup algorithm can distinguish the trivial ...
0
votes
0answers
40 views

Measurements in non-Abelian hidden subgroup algorithms

More than one measurement take place in a non-Abelian hidden subgroup algorithm. In this question, I would like to verify whether my understandings about them are right. I am using Andrew Childs' ...
0
votes
0answers
18 views

Choice of basis for non-Abelian hidden subgroup problems

I am going through QUANTUM MECHANICAL ALGORITHMS FOR THE NONABELIAN HIDDEN SUBGROUP PROBLEM by Grigni et al. In section 1.1 it is said that, It is still possible that a clever choice of basis ...
3
votes
2answers
99 views

Is there any hidden subgroup of a symmetric group which can be efficiently determined?

There have been a number of cases where efficient hidden subgroup algorithms have been found for specific non-Abelian groups with very specific structures. Why haven't we found any efficient quantum ...
3
votes
0answers
72 views

Why hidden subgroup problem is easy for very large subgroup?

I am going through QUANTUM MECHANICAL ALGORITHMS FOR THE NONABELIAN HIDDEN SUBGROUP PROBLEM by Grigni et al. On page 2, it is said that solving the hidden subgroup problem becomes very easy when the ...
9
votes
1answer
228 views

BQP algorithm for two graph bisection problems and its implications on NP $\subseteq$ BQP

I read the paper Ahmed Younes, "A Bounded-error Quantum Polynomial Time Algorithm for Two Graph Bisection Problems", 2015. doi:10.1007/s11128-015-1069-y which is published in Springer's journal ...
0
votes
1answer
52 views

Question about discarding the second register in the standard approach of hidden subgroup algorithm

My questions: What does discarding the second register mean for the standard approach of hidden subgroup algorithm? Why does discarding let the first register end up in a mixed state? My ...
-3
votes
1answer
125 views

Dimension of the Fourier transform for $S_5$ [closed]

My question: What is the dimension of the Fourier transform for $S_5$? My effort: The dimensions of the seven irreps of $S_5$ are $1,1,4,4,5,5,6$. According to the notes of Andrew Childs, the ...
0
votes
0answers
74 views

Fourier transformation of the automorphism group of a graph

Following is an example of permutation cycle graph $\Gamma$ for a given permutation $\pi = \left(1\text{ } 2\right) \left(3\text{ } 4\text{ } 5\text{ } 6\right)$. The adjacency matrix $A$ is given ...
2
votes
2answers
227 views

Consequences of $NP\subseteq P/poly$ to $BQP$

A post here Consequences of $BQP \subseteq P/poly$? queried on Consequences of $BQP \subseteq P/poly$. It is not known if $NP\subseteq BQP$. In general, what are the consequences of $NP\subseteq P/...
1
vote
0answers
47 views

First register in the hidden subgroup representations of Simon's and graph isomorphism problems

The Simon's problem involves a function which takes binary strings as inputs. One seeks to find the period of the function which acts on those inputs. In the standard method, the first register has ...
6
votes
1answer
159 views

Quantum Hardness of Approximating Lattice Problems

A common claim in lattice-based cryptography is that cryptosystems based on the Learning with Errors ($\mathsf{LWE}$) problem are hard to break (for a per-system definition of "break") for quantum ...
17
votes
0answers
244 views

Quantum Hardness of Finding Nash Equilibria

This question is inspired by the recent, beautiful work On the Cryptographic Hardness of Finding a Nash Equilibrium by Bitansky, Paneth, and Rosen. Their main result is that the existence of ...
0
votes
0answers
69 views

What is the relationship between quantum tomography and quantum error correction?

To realize correct quantum computing it seems that both quantum error correction and quantum tomography would be necessary. Is this true? What is the relationship between these two fields?
0
votes
0answers
40 views

Exponential acceleration of quantum metropolis sampling

In this paper (http://arxiv.org/abs/0911.3635), they propose a quantum MCMC algorithm. My question is whether they achieve exponential (or polynomial) acceleration compared with the classical ...
0
votes
0answers
50 views

Complexity of quantum shuffle transform

I define the shuffle permutation matrix by quoting from Hoyer first. Shuffle permutation matrix: The shuffle permutation matrix of dimension $mn \times mn$, denoted by $\Pi_{mn}$ as shorthand for ...
3
votes
0answers
54 views

Quantum annealing or adiabatic quantum optimization with continuous optimization problems

How do quantum annealing or adiabatic quantum optimization deal with continuous optimization problems such as SDP?
5
votes
1answer
147 views

Evidence that there is some problem in BQP distinct from BPP?

Are there any evidences (1 physics, 2 mathematics AND 3 computer science) that particular problems such as integer factorization, discrete logarithm are in BQP but not in BPP? There do not seem to be ...
1
vote
0answers
102 views

Is Logic Done on Superpositional Bit Values Useful?

Let's say I have a way to represent $N$ bits such that those bits are in a superposition of the $2^N$ possible states those bits can have and that I can do XOR and AND on those superpositional bits to ...
5
votes
1answer
161 views

How Much Computing Power would be Required to Fully Simulate a Cubic Meter?

Imagine you want to simulate a cubic meter down to the particle. By following the Standard Model and other basic physical equations, how much computing power would be required to do this, in say, a ...
3
votes
0answers
52 views

Does simulating chiral gauge theories lie within BQP?

In theoretical physics, there is a branch of quantum field theory dealing with chiral gauge theories. It has been conjectured by Feynman [1] and others that all quantum field theories can be simulated ...
3
votes
0answers
100 views

Two questions on Shor's algorithm

Does Shor's algorithm produce factors of a $n$-bit number and discrete log modulo $n$-bit prime in $O((\log n)^{2+\epsilon})$ bit operations using fast multiplication? I am trying to read from ...
2
votes
1answer
98 views

Verifying Shor's quantum error correction code

I know that Shor's 9 bit code can correct phase or bit flip, but I'd like to show that it can correct any type of error on a single qubit. I know that an arbitrary error can be expressed with the ...
1
vote
1answer
165 views

How does one determine if a mixed bipartite quantum state is entangled or not?

My question is based on the structure of the NP-hardness proof in section 6 (page 17) of this paper, http://arxiv.org/pdf/quant-ph/0303055v1.pdf Mathematically one can think of being given a ...
2
votes
0answers
65 views

Claw finding using quantum walk: superposition for Szegedy's framework

Within Claw Finding Algorithms Using Quantum Walk there is the subroutine $claw_{detect}$ described. As in above paper: Let $J_f(N, l)$ and $J_G(M, m)$ be Johnson graphs. Let $F$ and $G$ be vertices ...
16
votes
1answer
492 views

Why does Odlyzko improvement of Shor's Algorithm reduces the number of trials to $O(1)$

In his 1995 paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor discusses an improvement on the order-finding part of his ...
3
votes
1answer
404 views

If BQP contains NP, does this mean that P=NP?

There is a question raised by Scott Aaronson in one of his papers [1]: "Could we show that if NP ⊆ BQP, then the polynomial hierarchy collapses?". Assuming the answer is yes, and it is also know that ...
11
votes
1answer
594 views

Problems with no known quantum advantage

I was wondering what the list of current natural computational problems is for which there is no known complexity advantage in using a quantum computer. To start things off, I think computation of ...
8
votes
1answer
320 views

Is it conceivable at all that the standard model of physics can outperform a quantum computer in any sense?

The Standard Model of physics (the mathematical model which predicts the Higg's boson) is, as far as I understand, our most complete model of the universe. That is to say, it is the best description ...
6
votes
2answers
356 views

Suppose $\mathbf{P} = \mathbf{BQP}$. Then what is randomness? Would it even exist at all?

DISCLAIMERI do apologize in advance if this question turns out to be silly, for some trivial reason that I may be overlooking in this moment. Suppose for a moment that $\mathbf{P} = \mathbf{...