Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

Filter by
Sorted by
Tagged with
2
votes
0answers
101 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 ...
2
votes
0answers
96 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 ...
2
votes
0answers
93 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 ...
2
votes
0answers
94 views

Proofs to verify quantum states without revealing their description

Consider the following function $$f_s: k \rightarrow \lvert \psi_k \rangle$$ where $s,k$ are bit strings, and $\lvert \psi_k \rangle$ is a $n$-qubit state. Assume the function is a one-to-one mapping....
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
1
vote
2answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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? ...
1
vote
1answer
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 ...
1
vote
1answer
127 views

Is $CAPP \in P$ known to collapse some quantum complexity classes to classical ones?

Lets define the class $ZBQP = \{ L \mid \exists \textit{P-uniform circuit family } \{C_i\}, \forall n \in \mathbb{N}, |x| = n, |\langle 0|C_n|x \rangle - I(x \in L)| \leq 9/10 \Longleftrightarrow x \...
1
vote
1answer
85 views

Running multiple rounds of a BQP computation, without multiple measurements? [closed]

BQP as usually defined is: the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. Just like BPP, the choice of 1/...
1
vote
1answer
82 views

Quantum circuit simulation divergence in results

I'm learning about quantum computing in order to code a simulator. I tried the following circuit in Quirk And ran the same circuit using OPENQASM 2.0: Notice that the input is |11> in both cases, ...
1
vote
1answer
58 views

Iterating over all stabilizer operations on $k$ qubits

Stabilizer circuits, i.e. quantum circuit that only use the $H$, $\sqrt{Z}$, and $CNOT$ gates, can only implement a finite subset of all possible unitary operations. I want to iterate over all these ...
1
vote
1answer
58 views

QPIP minimal client quantum capabilities

It is conjectured that classical (BPP) client blind quantum computing is implausible according to Aaronson et al: https://www.researchgate.net/publication/...
1
vote
1answer
634 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
111 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
191 views

What is the Quantum Cheshire Cat experiments' import to Quantum Computing?

What is the significance of the Quantum Cheshire Cat to Quantum Computing? To recap, the Quantum Cheshire Cat experiment proved it was possible to separate a neutrons' spin from the neutron. Or, in ...
1
vote
3answers
293 views

Why is finding the ground state of a Hamiltonian in QMA?

Why is finding the ground stte of a Hamiltonian in QMA? It's in QMA to figure out if a hamiltonian has any energy eigenvalue within a certain window range which is at least inverse polynomial in size....
1
vote
1answer
214 views

Ising spin vs Pauli spin matrices [closed]

Are Ising spins scalar or operators? I am not a condensed matter physicist hence having some confusion. I have learnt about Ising models from adiabatic quantum algorithm papers. For example this ...
1
vote
2answers
207 views

Which cryptographic protocols are secure against quantum computer attacks?

Are there any cryptosystems that we know that would be secure against an attack by a quantum computer? Are there problems which are known or suspected to be hard for quantum computers, and can these ...
1
vote
1answer
137 views

Complement for joint POVMs?

I'm trying to relate some notions of set theory to POVMs. I firstly explain the scenario with set theory and then in the POVM setting. For some finite $N \in \mathbb{N}$, let $A_i$ and $B_i$ for $i=1,...
1
vote
1answer
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 = ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
746 views

BQNC and Abelian Hidden Subgroup Problem

We know integer factorization is in $BPP^{BQNC}$ from Cleve and Watrous. Is Abelian Hidden Subgroup Problem also in $BPP^{BQNC}$? In particular is Discrete Logarithm in $BQNC$ or at least in $BPP^{...
1
vote
0answers
66 views

Query complexity of quantum search with measuring oracle

Consider the following problem: Let $x\in X$ be a uniformly random value. Let $O$ be an oracle that measures whether the register $Q$ contains $x$. More precisely, $O$ measures $Q$ using the ...
1
vote
0answers
129 views

QUBO formulation of a discrete-variable 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 non-linear real-valued function $f:S \to \mathbb{R}$ which takes ...
1
vote
0answers
62 views

What is the average sensitivity of a quantum circuit with depth $d$ and size $s$?

We have some quantum circuit $C$ with $k$ ancillae and $n$ input bits of depth $d$ and size $s$, and we can define a function $f$ which, for any $x \in \{0, 1\}^n$, is the random variable which is the ...
1
vote
0answers
96 views

Is there a way to extract the mean from a quantum superposition?

Given the superposed output of some quantum computation, suppose I want to know the mean state, i.e. the mean probability of each qubit sampled over all states. The most obvious way to get this is ...
1
vote
0answers
123 views

Connection between diamond norm and output purity norm

Setting of the problem: Given a quantum channel $\mathcal{E}: \mathcal{H}_A\rightarrow \mathcal{H}_B$ (where $\mathcal{H}$ refers to a Hilbert space and subscript refers to the quantum register ...
1
vote
1answer
80 views

Finding a basis for quantum measurement with maximum distinguishability

I wish to find a basis state for the quantum measurement of two states which provides the maximum possible distinguishability. In this example let's say we wish to find the best basis ($|\psi\rangle$) ...
1
vote
0answers
80 views

How to simulate the quantum measurement of a quantum state in Quantum Image

I'm trying to implement (simulate) the Novel Enhanced Quantum Representation (NEQR), which is one of the quantum image representation models, but i'm stuck in the measurement part. In other words i ...
1
vote
0answers
119 views

Quantum polynomial method and L2-norm

Consider a quantum query algorithm that takes as input $x \in \{0,1\}^n$. Denote by $X_i$ the variable that evaluates to $1$ on input $x$ if the $i$-th bit of $x$ is 1, and $-1$ otherwise. Let $X_{\...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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?
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
34 views

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 ...
1
vote
0answers
93 views

Non-Transversal Fault Tolerant Gate

I have always heard that transversality is a sufficient, not a necessary condition for fault-tolerance in quantum computation. However, I have never seen any examples of non-transversal fault tolerant ...