Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

2
votes
0answers
96 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 ...
23
votes
1answer
1k views

Is the 2016 implementation of Shor's algorithm really scalable?

In the 2016 Science paper "Realization of a scalable Shor algorithm" [1], the authors factor 15 with only 5 qubits, which is fewer than the 8 qubits "required" according to Table 1 of [2] and Table 5 ...
-4
votes
1answer
125 views

Can a computer generated organism be self aware? [closed]

Imagine that a computer generating a small universe similar to our own. Same table of elements, same physics, ect. Starting from the very beginning, with the creation of all the atoms in the ...
-3
votes
1answer
178 views

The factoring problem reduces to order finding or is it the other way around? [closed]

initially i was not at all equipped in theoretical computer science and knew only basics of number of theory. I started working from scratch on the age old problem of primality testing which led me to ...
5
votes
1answer
254 views

Which areas of computer science have lots of overlap with physics?

I'm an undergrad in computer science but I've always loved physics and its ability to constantly amaze and surprise us about our world. I am wondering if there are areas in graduate level computer ...
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 ...
4
votes
0answers
97 views

Why primitive rotation is $53.13^\circ$ in the quantum Turing machine used by Vitanyi for Quantum Kolmogrov Complexity?

Right now I am going through Quantum Kolmogorov Complexity Based on Classical Descriptions by Vitanyi. In the introduction, the author assumed the primitive rotation $\theta = 53.13^\circ$ to have ...
0
votes
0answers
148 views

Questions about the definition of the Quantum Turing Machine

I am trying to have a better understanding of the definition of the Quantum Turing Machine. My questions: If the output of a quantum program is the eigenvalue of the ground state of a Hamiltonian ...
28
votes
2answers
3k views

Do any quantum algorithms improve on classical SAT?

Classical algorithms can solve 3-SAT in $1.3071^n$ time (randomized) or $1.3303^n$ time (deterministic). (Reference: Best Upper Bounds on SAT ) For comparison, using Grover's algorithm on a quantum ...
1
vote
0answers
99 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 ...
3
votes
1answer
124 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 ...
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
0answers
38 views

Non-commutative quantum counting with aggregate constant work per increment

Classically, it's very easy to create an incrementing function that can perform up to $n$ increments with $O(n)$ work: ...
-2
votes
1answer
1k views

Addition on a quantum computer

From reading https://arxiv.org/pdf/quant-ph/0008033v1.pdf 3n qubits are required to add two n bit numbers. For a simple arithmetic operation such as a+b+c+d where ...
3
votes
2answers
336 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 ...
0
votes
1answer
95 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 |...
7
votes
1answer
844 views

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

Update (January 2018) A new very interesting paper with various experiments on the IBM machine is Five Experimental Tests on the 5-Qubit IBM Quantum Computer by Diego García-Martín, Germán Sierra. ...
1
vote
1answer
609 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
68 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 ...
4
votes
1answer
323 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
68 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
93 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 ...
12
votes
1answer
196 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. ...
3
votes
2answers
444 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 ...
1
vote
0answers
112 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 ...
2
votes
0answers
91 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
141 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?
2
votes
1answer
174 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
101 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
71 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 ...
3
votes
2answers
122 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 ...
2
votes
0answers
94 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 ...
8
votes
1answer
267 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
83 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
135 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 ...
3
votes
2answers
300 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
52 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 ...
7
votes
1answer
248 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
406 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
93 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?
3
votes
0answers
95 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?
6
votes
1answer
212 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
106 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
250 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
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 ...
4
votes
0answers
170 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
266 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 ...
3
votes
1answer
258 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 ...
2
votes
0answers
92 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 ...
19
votes
1answer
824 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 ...