We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

Filter by
Sorted by
Tagged with
3
votes
2answers
346 views

When is a non-unitary quantum system only theoretical?

Suppose we construct a non-unitary quantum system α in hilbert space. It entails that this system would have no direct parallel in quantum circuitry as it is a requirement that all quantum gates ...
3
votes
1answer
177 views

String theory based computations

I was reading Arora and Barak's book on computational complexity and in the section on 'criticism on Turing machine model and the class P' along with quantum computer it also mentions possibilities of ...
3
votes
2answers
454 views

Numerical accuracy of superpositions in quantum computers

I am new to the topic of quantum computers (though I am very familiar with both quantum and computers, and I have studied Shor's paper about his eponymous algorithm at some point). Still, I have the ...
3
votes
1answer
174 views

Efficient generation of permutational invariant quantum states

Starting from $|00\cdots 0\rangle$, can permutational invariant quantum states, i.e. the following one: $$ |\psi_n\rangle = \frac1{n!} \sum \prod_{\pi\in S_n} |\pi(0)\rangle|\pi(1)\rangle\cdots|\pi(n-...
3
votes
1answer
165 views

Qubit gates in google supremacy

The gates in quantum supremacy experiment are nearest-neighbor and have spatial locality. Would this additional information help bolster IBM's argument to perhaps simulate quantum supremacy experiment ...
3
votes
1answer
462 views

Is the D-Wave architecture a close implementation of quantum interactive proof?

A very high level architecture is, as mentioned here, shown in this picture. The component on the left is classical while the one on the right is the D-Wave box. I understand that in QIP, Arthur is ...
3
votes
1answer
279 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 positive ...
3
votes
1answer
154 views

How well can an arbitrary (unknown) quantum state be imperfectly cloned?

How well can an arbitrary unknown (quantum) state $\rvert \psi \rangle = \alpha\rvert 0 \rangle + \beta \rvert 1 \rangle$, be imperfectly/approximately cloned? Given an unknown state ${\rvert \psi \...
3
votes
1answer
92 views

Questions about Farhi's pre-Adiabatic paper

I have been going through Eddie Farhi's 6-pages long pre-Adiabatic paper, An Analog Analogue of a Digital Quantum Computation. I guess I understand most of the math and physics but I am struggling ...
3
votes
1answer
134 views

Given a subset of of the hypercube and an affine transform of it, find the affine map

This is a follow up to this resolved question. Suppose we are given a set of bitvectors $A\subseteq\mathbb{F}_2^d$ and an invertible affine transformed copy of it $$B=\{Mx + s\mid x\in A\}$$ for some ...
3
votes
1answer
141 views

Papers on using resource states to implement QFT efficiently

I recently stumbled onto the idea of using a pre-existing re-usable phase gradient to implement the QFT, instead of having to keep re-applying exponentially precise phase gates. I'm looking for papers ...
3
votes
2answers
128 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
1answer
87 views

Clarification for argument in proof of search in N^1/3 queries with hidden variables/non-collapsing measurements

Let $N=2^n$. In Aaronson's Quantum Computing and Hidden Variables (1) and the recent follow up by Aaronson, Bouland, Fitzsimons, and Lee The space "just above" BQP (2), we consider models of ...
3
votes
1answer
254 views

Background Required to understand Quantum Monte Carlo techniques?

I'm trying to decide whether or not to do a project for a professor. The project involves writing a survey paper (of high enough quality to get his research group up to speed for a peripheral project)...
3
votes
1answer
280 views

The relationship between QCMA and QMA in the Turing and Communication model

First my background about computational complexity is still beginner. Recent paper published by Klauck and Podder [KP14] show that for the first time an exponential gap between computing partial ...
3
votes
1answer
135 views

Complexity class for quantum computer with commutative gates

BQP 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. In quantum computer allowed operations can be ...
3
votes
1answer
163 views

Why spectral norms are used for computing the complexity of adiabatic Hamiltonian?

In the context of adiabatic quantum computation the spectral norm was first used in the first adiabatic paper by Farhi et. al. when he demonstrated the relation of it to the conventional quantum ...
3
votes
2answers
454 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 ...
3
votes
1answer
181 views

Understanding efficient classical simulation of quantum computing

I want to understand the Gottesman-Knill theorem, which basically says that using some subclass of unitary transformations (from the Clifford group) there is no quantum speed-up ie. we can simulate ...
3
votes
0answers
194 views

In light of Raz and Tal's results, what can we say about whether there's a BQP problem for each level of the polynomial hierarchy?

[cross-posted on QCSE a couple of weeks ago] Every Venn diagram or Hasse diagram I see illustrating the "standard model" of computational complexity describes a universe of $\mathsf{PSPACE}$ problems,...
3
votes
0answers
119 views

What can be some bachelor thesis ideas in Quantum random walks?

Note: Cross-posted on Quantum Computing Stack Exchange. I am an undergraduate, reading about quantum information and quantum technology. For about some time, I have been interested in the ...
3
votes
0answers
57 views

Hardness of ancilla free quantum circuit extraction from circuit with ancillas

Is there any known result regarding the hardness of the following problem: Given a quantum circuit with ancillae implementing a unitary, find a quantum circuit that does not use any ancillae that ...
3
votes
0answers
226 views

Convexity argument in QMA Amplification

I'm interested in the basic amplification procedure for QMA: the prover sends $O(r)$ copies of his witness to the verifier, which decreases the error probability to $2^{-O(r)}$ (Chernoff bound). The ...
3
votes
0answers
99 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?
3
votes
0answers
61 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
158 views

Are NQP and QMA comparable?

Both definitions try to create a quantum analog for NP. NQP's definition comes from non-deterministic algorithms: it contains languages for which a Quantum Algorithm accepts with non-zero probability ...
3
votes
0answers
199 views

Environment-assisted quantum transport computation

The paper below and the news story based on it describe a new form of computation based on what they call environment-assisted quantum transport (ENAQT). ENAQT involves a combination of quantum and ...
3
votes
2answers
313 views

Impacts of quantum computing on Theoretical Computer Science [closed]

Using quantum computers we can do calculations very fast. However from a layman's view, I want to know the impact of quantum computers have on Theoretical computer science.
3
votes
0answers
110 views

Polynomial Quantum Algorithm for Graph Isomorphism? [duplicate]

Possible Duplicate: NP-intermediate problems with efficient quantum solutions Many suspect that quantum computers will not be able to efficiently solve NP-complete problems and thus focus on the ...
2
votes
2answers
368 views

Time-entanglement phenomenon

Please let me mention certain idea here, although it is probably vague (and new, at least as related to experiment mentioned below, as far as I know). The general notion of algorithm is model of ...
2
votes
1answer
1k views

Differences between Quantum Computing and Parallelism [closed]

What are the differences between Quantum Computing and Parallelism? thanks in advance
2
votes
1answer
95 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 ...
2
votes
1answer
2k views

Is quantum annealing faster than simulated annealing/genetic/other state-of-the-art optimization algorithms?

There's the idea of quantum annealing being used to solve optimization problems in terms of a QUBO problem for D-Wave's quantum algorithm. I understand that the advantage of quantum annealing as ...
2
votes
1answer
88 views

Why is it impossible to work with polylog length encoding schemes for quantum circuits?

I am going through Quantum Computational Complexity by John Watrous. On page $12$, he said: The encoding disallows compression: it is not possible to work with encoding schemes that allow for ...
2
votes
1answer
127 views

Lower bound on alternations needed in $BQP$ versus $PH$ result?

What is the fastest $f(n)$ the relatively new result of oracle separation of $\mathsf{BQP}$ from $\mathsf{PH}$ provides such that ${\#\mathsf{SAT}}\not\subseteq\mathsf{FP}^{\mathsf{PH}[O(f(n))]}$ ...
2
votes
1answer
506 views

Continued Fraction Algorithm in Shor's Algorithm

I am just trying to make the final link of Shor's algorithm clear. Here $r$ is the order of $x$ modulo $N$. We have a number $\psi$, which for a rational number $\dfrac{s}{r}$ satisfies \begin{...
2
votes
1answer
181 views

Why are sub-normalized states studied in quantum computation?

By basic postulates of QM, any state of a system is described by a normalised density operator. Now i fail to see why people study sub-normalized states ( e.g.: In generalised fidelity etc). I'd be ...
2
votes
1answer
2k views

Using MATLAB's CVX Package for Semidefinite Programming in Quantum Information

I'm attempting to formulate the semidefinite programs used in the paper "Hedging Bets with Correlated Quantum Strategies" (specifically those on page 7) into CVX so that I can play around with the ...
2
votes
1answer
327 views

Simulating quantum measurements by unitaries

I have seen many papers in which quantum measurements are assumed to be replaced by unitaries. See this quotation from [KW00] for instance: Often we will describe quantum circuits in a high-level ...
2
votes
1answer
151 views

Is graph automorphism Karp-reducible to graph isomorphism under hidden subgroup representation?

The classical representations of the graph automorphism problem is Karp-reducible to the classical representation of the graph isomorphism problem. The sketch of proof for this can be written as ...
2
votes
1answer
177 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 ...
2
votes
1answer
268 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 ...
2
votes
1answer
789 views

Complexity: simulated annealing vs. quantum annealing

How do I compare the performance of simulated annealing against the performance of quantum annealing algorithms? In Convergence theorems for quantum annealing by Morita and Nishimori, it has been ...
2
votes
1answer
1k views

A quantum algorithm for GCD

Does anyone know of a direct quantum algorithm for computing GCD, - There could be quantum gates for addition subtraction constructed explicitly, using CNOT, etc. - the construction can be done in ...
2
votes
2answers
878 views

Quantum oracle implementation overhead

I am a physicist getting acquainted with one of the typical constructs for formulation and analysis of quantum algorithms (such as search problems or query complexity models), namely the "oracle ...
2
votes
0answers
60 views

Quantum advantage beyond the black-box model

The common quantum algorithms I know of can be all explained using black-box model (i.e., query model): Grover's search. An $O(\sqrt{n})$-query algorithm that computes the OR of $n$ bits. Shor's ...
2
votes
0answers
71 views

Quantum security of cryptosystems

One of the main candidates for PQ cryptography is code based cryptography (other than lattice based). The Niederreiter cryptosystem based on goppa codes is shown to be resistant to hidden subgroup ...
2
votes
0answers
59 views

A random ensemble of sparse boundary operators

The following question arises from the study of quantum error correction, and high-dimensional expanders: Is there an algorithm that for given numbers $n>0,d≤n,r≤n$ samples uniformly a linear ...
2
votes
0answers
150 views

Computational Complexity of cycle double cover

Let $\mathcal{G}$ be the set of all finite simple graphs. Let graph $G\in \mathcal{G}$ and $C_G=\left <C_1,...,C_m \right >$ be a sequence of cycles of $G$ for some $m$. For every edge $e$ of $G$...
2
votes
0answers
98 views

Cutting edge of quantum error correction

Often I find myself needing to know the best error correcting code for a certain quantum scenario. For example, suppose my logical systems are 3-dimensional; then what's the most efficient encoding to ...