Questions tagged [classical-computing]

For questions about the relation between quantum computing and classical computing, such as their relative performance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
17 views

Why does having two classical registers sometimes only yeild one bit?

I was running some qiskit code on qasm_simulator to test something and I realized that, when I have two separate classical registers, sometimes only one bit is generated, and I'm trying to understand ...
user avatar
1 vote
1 answer
30 views

How does Fujitsu's digital annealer work?

I have read Fujitsu's white paper for a brief introduction to their device: http://marketing.us.fujitsu.com/rs/407-MTR-501/images/quantum-inspired-computing.pdf As far as I know, Fujitsu's hardware is ...
user avatar
  • 33
0 votes
0 answers
14 views

determine degree of boolean polynomial given as black box

I searched a lot but couldn't find a good resource that addresses this question. Given a boolean polynomial with $n$ boolean variables as a black box, what is the most efficient way to compute its ...
user avatar
3 votes
2 answers
131 views

Are qubits just analog, continuous classical bits? [duplicate]

Topologically, classical bits (cbits) are essentially special cases of qubits restricted to the poles of the Bloch sphere. However, this restriction doesn't seem to be classical per se, but is simply ...
user avatar
  • 131
2 votes
0 answers
21 views

Best classical algorithm for period finding on finite Abelian groups

Given a finite Abelian group $G = \prod_{j=1}^n \mathbb{Z}_{m_j}$ with $m_j \geq 2$ and a function $h: G \to \mathbb{C}$ that is $s$-periodic. I have already proven that for all $\xi \in G$ we have $\...
user avatar
1 vote
1 answer
175 views

Would the interest in building quantum computers decrease if a classical algorithm for factoring all integers in polynomial time is discovered?

Quoting Wikipedia: No algorithm has been published that can factor all integers in polynomial time, that is, that can factor a $b$-bit number $n$ in time $O(b^k)$ for some constant $k$. Neither the ...
user avatar
  • 205
4 votes
1 answer
69 views

Will standard programming languages be applicable for quantum computing?

I'm new to quantum computers and computing, so it's possible my question is pointless or unnecessary ... but what about current programming languages such as Java, C++, Python in terms of quantum ...
user avatar
  • 173
7 votes
1 answer
153 views

Circuit from finite group of gates and classical simulations

Let $ G $ be a finite group of quantum gates. Is it true that any circuit made using only gates from the finite group $ G $ can be efficiently simulated on a classical computer? Here by circuit made ...
user avatar
1 vote
0 answers
29 views

Can a Hankel matrix $H$ be efficiently decomposed into a linear combination of unitaries (LCU), so that $H=\sum_k a_k U_k$

Suppose I have a Hankel matrix of arbitrary size $N\times M=2^n\times 2^m$ for integers $n<m$ (the qubit numbers of two circuits I have at my possession), given by: $H=\begin{pmatrix}x_1&x_2&...
user avatar
  • 51
6 votes
1 answer
140 views

What is the relationship between the size of the Hilbert space for boson sampling and the complexity of classical simulating it?

My intuition is that the fastest classical algorithm for simulating some kind of noiseless quantum sampling process should scale roughly with the dimension of the Hilbert space: you would need to ...
user avatar
  • 2,107
5 votes
1 answer
150 views

Has the possibility of there being a classical cryptography algorithm able to withstand quantum computing been proven?

Has it been proven, that a classical codec (encoder-decoder) (classical meaning one that doesn't require a quantum system for its operation) is possible, such that a quantum computer cannot crack it? ...
user avatar
4 votes
2 answers
72 views

Can error correction for a classical algorithm with bit flips be easier than for a general quantum circuit?

Assume one runs a purely classical algorithm on $n$ logical qubits on a physical device with some bit flip probability. Can implementing error correction in this case be any easier than in the case of ...
user avatar
  • 1,478
2 votes
2 answers
160 views

Are there problems that a classical computer can solve and a quantum computer can never solve?

Apologies if this is a silly question. But I've heard quantum computers can solve problems that classical computers can't. What about the converse, are there any problems that a classical computer can ...
user avatar
1 vote
0 answers
48 views

Why is sampling considered difficult on a classical computer but easy on a quantum computer? [closed]

It is my understanding that classical computers have a hard time sampling results from an output from a quantum circuit, but quantum computers find it very easy to do so. Why is this?
user avatar
  • 97
1 vote
1 answer
76 views

What are the types of models of computation aside from the quantum query model?

It looks like in a lot of quantum algorithms, we use the quantum query model. I wanted to know what are the other types of models of computation, used in quantum computing as well as in classical ...
user avatar
  • 23
1 vote
1 answer
54 views

What is the counting argument for the number of elementary operations required for a random function?

What is the counting argument for the following statement (classical)? "A random function on n bits requires $e^{\Omega(n)}$ elementary operations." It appears in the introduction of PRL 116,...
user avatar
8 votes
5 answers
3k views

Why can't quantum computation replace classical computation?

I am not a total novice of quantum computation (have read the first 6 chapters of Nielsen and Chuang, though not familiar with every part), but there are some fundamental questions that I don't know ...
user avatar
12 votes
1 answer
2k views

Are circuits with more than 1000 gates common?

I have seen circuits with 30 qubits and around 500 gates. Also circuits with 32 qubits and 6000 gates. Are circuits with more than 1000 gates common in quantum computing? Are there many quantum ...
user avatar
4 votes
2 answers
112 views

Can the difference between quantum and classical circuits be attributed to different paths in the Hilbert space?

One of the explanations I have encountered for why quantum computation can provide speed-up over the classical is a picture that in the Hilbert space much more paths are allowed quantum-mechanically ...
user avatar
2 votes
0 answers
100 views

When is a Quantum Computer Slower Than a Classical Computer?

Someone offhandedly mentioned to me that quantum computers are sometimes significantly (I guess they meant asymptotically) slower than classical computers. Unfortunately, I didn't get any arguments ...
user avatar
4 votes
1 answer
61 views

Quantum computer speedups for classically efficient applications

I'm interested in learning about cases where a quantum computer could be used to perform tasks with only a constant (albeit large) factor of improvement in execution speed over classical computers. ...
user avatar
  • 4,667
4 votes
1 answer
187 views

Using principle of deferred measurement to replace gates conditional on classical bits (c_if)

I am trying to implement the Iterative Phase Estimation algorithm on one of Qiskit's labs. I can do it for a 'nice' phase, such as 1/4 : But if I want to implement the algo generally (as a subroutine ...
user avatar
3 votes
1 answer
82 views

What's the difference between open-source QRNG and Quantis Device?

qRNG is an open-source quantum random number generator written in python and Quantis RNG is a physical quantum random number generator. Both are capable of generating quantum random numbers, but how ...
user avatar
  • 31
3 votes
0 answers
56 views

Shor vs Schnorr: A classical algorithm for breaking RSA? [duplicate]

I am not sure why I haven't heard much chatter about this paper by Dr. Claus Peter Schnorr where he claims to have come up with a classical algorithm to break the RSA protocol. The construction is ...
user avatar
  • 221
8 votes
1 answer
504 views

Classical algorithm with complexity similar to Shor's discovered: Are there more efficient quantum algorithms than Shor's?

In the article Fast Factoring Integers by SVP Algorithms the author claims that he discovered classical algorithm for factoring integers in polynomial time. The Quantum Report mentioned here that it ...
user avatar
2 votes
0 answers
19 views

Are classical analogues of quantum computers using superposed waves possible? [duplicate]

The trick of quantum computing is to take the advantage of wave mechanics (superposition) and entanglement. This allows to perform parallel computations/manipulations with $2^n$ superposed waves for $...
user avatar
2 votes
2 answers
123 views

Generally speaking, are quantum speedups always due to parallelization of a given problem?

We know that quantum computers use the wave-like nature of quantum mechanics to perform interference. Sometimes we can use this interference to perform specific algorithms that will cause enough ...
user avatar
2 votes
2 answers
139 views

How do qubits in quantum computers work? [closed]

I was reading about quantum computers and qubits. While a classical bit can be either 0 or 1, a qubit can be 0 or 1 or both at the same time (can it be none too?). But how is this useful at all? If it ...
user avatar
7 votes
1 answer
91 views

what matrix operations have better known time complexity on a quantum computer?

I'm exploring quantum computers for a semester project. I'm mainly interested in making faster matrix calculations than a regular computer. I was wondering what arithmetic operations (irrespective of ...
user avatar
  • 71
6 votes
2 answers
2k views

Aren't qubits just ternary?

Qubits have 3 states: 1, 0, and 1 and 0 at the same time. If a qubit can have 3 states, then how come they are seen as different from ternary computing, which also has 3 states? Is it that the 3 ...
user avatar
  • 83
9 votes
5 answers
1k views

If quantum computing always return random measurement (or uncertain measurement), why do we still need it?

I am very new to quantum computing and currently studying quantum computing on my own through various resources (Youtube Qiskit, Qiskit website, book). As my mindset is still "locked" with ...
user avatar
2 votes
1 answer
183 views

No. of bits in 160 qubits computer [duplicate]

I read in a book that (https://hub.packtpub.com/quantum-expert-robert-sutor-explains-the-basics-of-quantum-computing/) 160 qubits (quantum bits) could hold $2^{160} \approx1.46\times 10^{48}$ bits ...
user avatar
3 votes
2 answers
122 views

Question on practical quantum computing programming code [duplicate]

Has anyone tried any quantum computing programming code that shows or demonstrates the advantage of a quantum computer over classical computers? Thanks a lot.
user avatar
4 votes
2 answers
518 views

Does 1 qubit correspond to 2 bits?

In a lot of presentation I always see people say that $n$ qbit are approximately $2^n$ classical bit. Those talks where oriented for a broad audience, so they left out a lot of things. Deep down I ...
user avatar
  • 153
3 votes
3 answers
193 views

Is there an explanation for why, to search through an unstructured database, the average number of checks is $\frac{N}{2}$ in classical computation?

I have came across many books online that all explain that if $N$ is large enough, then the average number of checks in $N/2$ but is there a mathematical explanation or derivation for why this is true?...
user avatar
  • 31
3 votes
1 answer
77 views

Papers on classical optimization in QAOA

Are there any papers on the classical optimization part of QAOA? What is the most efficient method now? And how is the classical optimization classified?
user avatar
  • 499
3 votes
0 answers
82 views

What is the best way to use loop statements on a quantum computer?

I am interested in solving a time dependent linear partial differential equation of the form $Ax=b$ which, in classical computing, would amount to looping over solutions of $Ax=b$ where $b$ is updated ...
user avatar
1 vote
0 answers
112 views

Can hash functions speed up quantum simulation? (Generalizing May and Schlieper's idea)

Recently May and Schlieper have published a preprint (https://arxiv.org/abs/1905.10074) arguing that the modular exponential register in Shor's algorithms can be replaced with a universally hashed ...
user avatar
  • 147
4 votes
2 answers
702 views

Can classical linear algebra solvers implement quantum algorithms with similar speed-ups?

A quantum algorithm begins with a register of qubits in an initial state, a unitary operator (the algorithm) manipulates the state of those qubits, and then the state of the qubits is read out (or at ...
user avatar
3 votes
2 answers
344 views

Is it possible to convert classical algorithms to quantum ones?

I am new in this field and I am considering to do research for my engineering degree. First, I would like to have an opinion from more experienced people. Do you think it is possible to convert ...
user avatar
0 votes
1 answer
73 views

What are some general concepts of how a classical computer would interface with a quantum computer?

Very general question so I'm not looking for an exact answer. I just want a basic description of certain ways it can be done and then if possible the names of those ways, so that I can look them up ...
user avatar
  • 145
4 votes
1 answer
121 views

STO-3G Basis Set

Can someone please explain why STO-3G is considered to be a good basis set for quantum computing, while it does not help in classical computing? I would also be very grateful for any references to ...
user avatar
7 votes
3 answers
520 views

Compiling a classical function to a quantum circuit in practice

It can be shown that any classical function $f$ can be implemented by a quantum circuit $Q_f$, so that $$ \sum_{x}|x,0^k\rangle \xrightarrow{\mathit{Q_f}} \sum_{x}|x,f(x)\rangle $$ where $f$ has $k$ ...
user avatar
  • 71
4 votes
2 answers
215 views

How does a classical computer simulate nonclassical correlations?

This may be a dumb question, if so please forgive me, it is late at night. I have learned that a classical computer can simulate a quantum computer in exponential time and space, but classical ...
user avatar
  • 297
3 votes
2 answers
327 views

Classical computations from restricted quantum gates

The CNOT gate together with phase shift gates for all possible angles are not universal for quantum computing. Are they also not universal for classical (reversible) computing? Is it possible to ...
user avatar
  • 133
8 votes
2 answers
360 views

Is it right to think of superposition as just angle?

Based on my current understanding, a qubit is represented as a vector $(a, b)$ which satisfy $a^2 + b^2 = 1$. Classical bit one can be represented as $(0, 1)$ and bit zero can be represented as $(1, ...
user avatar
5 votes
5 answers
401 views

Does a classical computer really require $2^n$ complex numbers to represent the state of $n$ qubit quantum computer?

One often reads that the key reason why classical computers (probabilistic or deterministic) are unable to simulate quantum algorithms such as Simon's or Shor's efficiently is that a classical ...
user avatar
  • 111
0 votes
1 answer
148 views

Can I learn Quantum Programming and then go back to learn the Mathematics / Physics behind it later?

Learning from the ground up (while great) is an overdose of the mathematics behind quantum computing and is taking way too long to grasp. I have a Computer Science / Programming background. I am ...
user avatar
2 votes
1 answer
104 views

CPTP, Kraus representation and classical registers

What is the best mathematical representation of a quantum system that has some classical registers and some quantum registers? I'm asking because I'm considering any "physical" process $\pi()$ that ...
user avatar
2 votes
3 answers
77 views

What does the $\sqrt{NOT}$ gate have to do with irreversibility?

In his essay "Why now is the right time to study quantum computing" Aram Harrow writes, after describing the action of the $\sqrt{NOT}$ gate, that: However, if we apply $\sqrt{NOT}$ a second time ...
user avatar
  • 245