# Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

337 questions
Filter by
Sorted by
Tagged with
101 views

53 views

### How the errors of the measured quantities of an adiabatic Hamiltonian are inversely proportional to the square root of the number of measurements?

I am going through the paper, Solving the graph-isomorphism problem with a quantum annealer, by Hen et. al. In the last line of the second paragraph of the second column of page 2, it says, Since ...
152 views

### Why is Shor's algorithm in $BPP^{BQNC}$ when needing to uncompute subprocedure call?

Why is Shor's algorithm in $BPP^{BQNC}$? It's true the quantum Fourier transform is in $BPP^{BQNC}$, but the algorithm needs to call a number theoretic function f which has period p which is a factor ...
156 views

### Quantum algorithm of graphs: How to create superposition of paths?

Let us allow path to have same vertexes in it. (defining) So suppose we have a graph of $N$ vertexes and we want to separate it into some superposition of paths that have $N$ vertexes (so if the ...
1k views

### From CHSH inequality to CHSH game

I have been going through Certifiable quantum dice: or, true random number generation secure against quantum adversaries by Umesh Vazirani and Thomas Vidick. They have used entangled particles as ...
867 views

### Are quantum computers turing complete? [closed]

I have gained some interest in quantum computing ever since I have been reading Scott Aaronson's blog. The fact that using this computational model, you would be able to factor integers in polynomial ...
353 views

### Quantum evolutions

I was reading Quantum Computation Explained to my Mother. While considering the following problem: Problem 1 Suppose we are given a mysterious boolean operator F (a black box) which takes one ...
266 views

### Running Simon's algorithm on D-wave machine

I was wondering whether Simon's algorithm could be run on a D-wave machine. The Simon's algorithm is a promise problem. On the other hand the D-wave machine can run only quadratic unconstrained ...
205 views

### Computational Library to compute Quantum Cluster States

I want to write a simulator for a quantum computing model that I am working on and I was wondering what would be the correct library / implementation strategy to implement quantum cluster states? ...
111 views

### How exactly is solving the random circuit sampling problem a computation in the Church-Turing thesis sense? [closed]

Note: This has been cross-posted to Quantum Computing SE. If we assume $\mathsf{BQP} \neq \mathsf{BPP}$, then we can say with reasonable certainty that Google's random sampling experiment falsifies ...
127 views

85 views

### PromiseBQP and expectation values of operators

This question is regarding The Equivalence of Searching and Sampling by Aaronson. In page 4 he makes the following statement, ... a difficult and unsolved meta-question is whether PromiseBPP = ...
376 views

### What would a quantum computer architecture look like? [closed]

More specifically, assuming we manage to make an efficient quantum switch, some kind of "quansistor"(quantum transistor) and manage to resolve the problem of joining a bunch of them together without ...
75 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 ...
73 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 ...
248 views

### 1st & 2nd quantization from TCS

Last year I attended Scott Aaronson's talk Hawking Quantum Wares at the Classical Complexity Bazaar. Being intrigued by his argument that "[e]ven if quantum mechanics hadn't existed, theoretical ...
262 views

### Branch prediction in quantum algorithms

Are there any good examples of branching efficiency / prediction in quantum algorihms? Specifically suppose I have a set of CNOT gates one after the other that have the control line on the same line ...
21 views

### whether two sets of stabilizer generators are related by a Clifford circuit

I have two stabilizer models each specified with a given set of generators. Let's call the two generating sets $S_1$ and $S_2$. By stabilizer model, I mean putting the generators on unit cells of a ...
70 views

### Complexity of enumerating over promise problems and circuits?

Given an enumeration over all Turing Machine which run with increasing length, is there a complexity class'' which describes the complexity of determining whether a given TM satisfies the promise ...
67 views

### Complexity class of approximating perfect match count

We know we can approximate perfect matching count of bipartite and approximate volume of convex bodies in randomized polynomial time. Is there any evidence these approximations could be in Nick's ...
746 views

110 views

### Two definitions of $QMA$

In this question, I am trying to understand the equivalence between the following two definitions of the complexity class QMA. In Quantum Computational Complexity, John Watrous defines the class QMA ...
122 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 ...
142 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?
54 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 ...
107 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 ...
### Coset state of $3$-node graph isomorphism problem
The hidden subgroup representation of a $3$-node graph isomorphism problem is defined over the symmetric group, $G = S_6$. So, any hidden subgroup algorithm that wishes to solve the problem should ...