Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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
2 votes
1 answer
38 views

What is the F12 rule for the Game of Life

This is more of a help call to find a specific rule set for the game of life. I'm currently reading the "Entanglement in the Quantum Game of Life", however they refere to the classical F12 ...
Qubii's user avatar
  • 191
4 votes
1 answer
42 views

Simulating any fixed time classical circuit in time poly(t) on a quantum computer

I'm analyzing the paper "Quantum walk algorithm for element distinctness" by Ambainis and at the bottom of page 24 (the last line of "Additional requirements" in section 6.2) ...
Thyrum's user avatar
  • 61
2 votes
1 answer
202 views

Classical computation required in Shor's algorithm: are they heavy?

A quantum computer also requires to perform classical computations. I would like to know if to implement Shor's algorithm, there is a heavy classical computation cost (i.e. that would require a ...
HelloMan's user avatar
  • 123
5 votes
2 answers
725 views

Are Quantum Computers Bad at Addition?

I recently built a dynamic full adder gate with Qiskit. The gate essentially copies the classical computing method for a full adder by emulating the classical gates e.g. AND == Toffoli (Quantum AND ...
Aidan's user avatar
  • 61
3 votes
0 answers
35 views

Is it safe to assume that any hybrid algorithm can be transformed into a purely quantum form with comparable complexity?

Suppose we have a definite function of interest from numbers to numbers (from a finite set). In general, we have a lot of options when we construct algorithms that compute it (with some errors, ...
Danylo Y's user avatar
  • 7,342
1 vote
0 answers
22 views

Quantum code for Substitution Box

How to write quantum code(qiskit) for n-bit Substitution Box with minimum number of gate and qubit.
Ausaf Hussain Akhlaq's user avatar
1 vote
1 answer
105 views

How can I Combine Qiskit's VQE Tutorial and TSP Simulator to solve the TSP on a real backend efficiently?

I have a university project where I am trying to solve the Traveling Salesman Problem by using a real quantum backend, rather than just the VQE simulator, as in this tutorial. I found this code on ...
Aidan's user avatar
  • 61
0 votes
1 answer
43 views

How should large quantum computers use Clifford simulators like Stim?

High-level architecture question: When we have the ability to do useful quantum computations with plenty of qubits, error correction and fault tolerance, do Clifford simulators still have a role to ...
user1936752's user avatar
  • 2,997
4 votes
3 answers
170 views

What is the computational power of classically mixed states?

It is my understanding that mostly one considers as the "classical" state, a single bit string (eg 00101), with a discrete number of deterministic gates applied to it. All computers that ...
Wouter's user avatar
  • 301
8 votes
1 answer
183 views

Is there a fast sparse Hadamard transform?

Suppose I give you an $n$-qubit state vector as a classical list of numbers (or as an oracle that can query the amplitudes). I tell you this state vector will contain exactly $k$ non-zero amplitudes, ...
Craig Gidney's user avatar
  • 37.7k
2 votes
1 answer
56 views

Quantum Computing and Overhead

Consider Grover's Algorithm, which identifies a specific $N$-bit string from the set of all $N$-bit strings. The string test function only has to be called $2^{\frac{N}{2}}$ times instead of $2^{N-1}$ ...
itere79's user avatar
  • 21
1 vote
0 answers
41 views

What are problems so computationally difficult that they'll likely only be solved with quantum computers? [duplicate]

Of course, there are the exceedingly well-known examples of this, eg. breaking RSI encryption, possibly protein folding, etc. What are some more obscure or overlooked ways that the greater computing ...
Nurdick's user avatar
  • 21
1 vote
0 answers
28 views

Who is currently working on coherent Ising machines (classical analog devices)?

Can you share some papers on that subject? Review papers would be highly appreciated. What are limitations in terms of connectivity between different spins?
sycramore's user avatar
  • 325
0 votes
1 answer
54 views

Why are quantum computing networks so far behind classical methods?

I'm new to quantum computing, and computing in general, but it seems like quantum computing networks are really lagging behind what we have achieved with classical networks. I know that there are ...
Mihir Macwan's user avatar
1 vote
1 answer
61 views

What does Quantum Circuit Wires and Separated mean?

From Quantum Circuits, there are two statements that are not clear. Quantum Circuits Quantum circuits are collections of quantum gates interconnected by quantum wires. The actual structure of a ...
Moo's user avatar
  • 153
3 votes
0 answers
37 views

Advantage of quantum computers over classical computers in fully modeling interactions between atoms?

I'm trying to better understand the advantage quantum computers offer in terms of their ability to more accurately model chemical reactions. As a way to come to a deeper understanding, my question is: ...
Poe's user avatar
  • 31
1 vote
1 answer
65 views

Could a quantum computer simulate any system based on different types of logic? [duplicate]

Quantum computing is based on quantum mechanics (obviously) which has different logical rules than classical/Boolean logic. However, does this mean that a quantum computer could simulate or process ...
vengaq's user avatar
  • 111
1 vote
0 answers
44 views

Is there research on leveraging quantum computing in the theory component of classical SMT solvers?

Satisfiability Modulo Theories (SMT) extends the concept of boolean satisfiability (SAT) by including theories such as arithmetic, arrays, bit vectors, and functions. In a typical SMT problem, a ...
Sami Liedes's user avatar
0 votes
1 answer
529 views

Can a quantum computer count up by 1 faster than a classical computer?

Let's say you want to generate all images of size NxN, black/white pixels. This is equivalent to counting from 0 to 2^(N^2)-1. ...
Bob's user avatar
  • 111
1 vote
2 answers
81 views

Can a classical circuit of size $2^k$ be modelled by a quantum circuit of size $k$ or vice versa?

There is something fundamental I don’t understand about quantum computing and hence the following question may be very trivial or stupid for which I apologize in advance. A boolean function $f:\{0,1\}^...
mrpotato's user avatar
0 votes
1 answer
373 views

Deutsch-Jozsa Algorithm - classical solution

so I'm self-studying quantum computing and have a question about the proposed classical solution to the Deustch-Jozsa problem. So given your function $f: \{0,1\}^n \rightarrow \{0,1\}$ say you were to ...
Proliferate309's user avatar
1 vote
0 answers
29 views

Find the minimal and maximal of $\widehat{S}_f (\rho \| U^* \sigma U)$

I have been study the minimal (maximal) of a $f-$divergence. Fumio Hiai introduced the $\widehat{S}_f (\rho \| \sigma)$ divergence in his article. $$\widehat{S}_f (\rho \| \sigma) := \text{Tr} \sigma^{...
Minh's user avatar
  • 111
0 votes
0 answers
53 views

What is reservoir computing in simple terms, and how can it be used with quantum computing?

For those who are familiar with the notion of Reservoir Computing, can you explain the concept with simple terms and how it can be used with quantum computing ?
Duen's user avatar
  • 426
4 votes
0 answers
139 views

Understanding the Gottesman-Knill Theorem

I come from a theoretical CS background, and I am trying to gain a better appreciation of the exact formal statement of the Gottesman-Knill theorem in terms that I am more familiar with. My question ...
trillianhaze's user avatar
2 votes
1 answer
73 views

Where is "quantum search" in the complexity hierarchy?

Grover's algorithm is one of the most popular quantum algorithms that solves the problem of "quantum search." But what is this problem, and what are its characteristics. When considering ...
Andrew Baker's user avatar
2 votes
1 answer
366 views

Is there something wrong with cross-entropy benchmarking, or is it still considered as a reasonable path towards quantum supremacy?

My question is strongly related with this one. Google's quantum supremacy claim uses Random Circuit Sampling. The principle is the following one: a realistic noise model for random circuits performed ...
Tristan Nemoz's user avatar
  • 6,462
3 votes
1 answer
456 views

How does one convert a truth table to a square permutation matrix?

Given a classical circuit of $m$ inputs and $n$ outputs, composed of various AND gates, OR gates, NOT gates, etc., a truth table is a $2^{m}\times(m+n)$-sized matrix, where, in general, the first $m$ ...
1 vote
0 answers
37 views

Applying a clock in quantum computing?

In quantum computing, I feel it mostly looks like designing hardware with Hardware Description Language (HDL) experience such as VHDL or Verilog. So the term program language for quantum computing ...
Muhammad Ikhwan Perwira's user avatar
3 votes
3 answers
1k views

Why do people say that Grover's algorithm does not parallelize well?

I've seen several sources, including NIST, claim that Grover's algorithm is unlikely to be useful for attacking a symmetric-key algorithm like AES-128 or a hashing algorithm because "Grover's ...
tparker's user avatar
  • 2,801
5 votes
4 answers
4k views

Why do computer scientists care about the phase of qubits?

When I design some classical register, flip-flop, binary counter, small byte of RAM, etc from scratch with classical logic gate, I never deal with such binary direction because classical bit doesn't ...
Muhammad Ikhwan Perwira's user avatar
3 votes
1 answer
332 views

Can there be an equivalent classical circuit for a quantum circuit?

It is known that any classical circuit or algorithm can be implemented on a quantum computer using universal quantum gates. My question is, can there be a circuit with classical statistics which are ...
Discord Warrior's user avatar
1 vote
2 answers
632 views

Is there any real world problem where I can see quantum computing being better than classical computing?

Is there any paper or piece of code showing, on a REAL quantum computer, that a specific real world problem (possibly related to computer science, machine learning or finance and possibly NOT related ...
mpro's user avatar
  • 517
2 votes
1 answer
239 views

What are the practical advantages of quantum GANs with respect to classical ones?

I read some papers on Quantum GANs, for instance this one and this one. I also noticed all the main quantum computing frameworks have a tutorial on quantum GANs, e.g. qiskit. However I don't really ...
mpro's user avatar
  • 517
1 vote
1 answer
123 views

Prove that classical counting requires $k=\Omega(N)$ oracle calls

Consider a classical algorithm for the counting problem which samples uniformly and independently $k$ times from the search space, and let $X_1, ... ,X_k$ be the results of the oracle calls, that is, $...
Sooraj S's user avatar
  • 831
0 votes
1 answer
32 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 ...
YaGoi Root's user avatar
1 vote
1 answer
547 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 ...
CW Lino's user avatar
  • 35
3 votes
2 answers
211 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 ...
Tfovid's user avatar
  • 131
2 votes
0 answers
31 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 $\...
mrwarrdy's user avatar
1 vote
1 answer
255 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 ...
blunova's user avatar
  • 201
4 votes
1 answer
408 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 ...
Mikolaj's user avatar
  • 173
7 votes
1 answer
213 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 ...
Ian Gershon Teixeira's user avatar
1 vote
0 answers
56 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&...
JoJo's user avatar
  • 99
7 votes
1 answer
324 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 ...
tparker's user avatar
  • 2,801
5 votes
1 answer
228 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? ...
Shahid Khan's user avatar
4 votes
2 answers
149 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 ...
mavzolej's user avatar
  • 1,951
2 votes
2 answers
720 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 ...
More Anonymous's user avatar
1 vote
0 answers
94 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?
chois3's user avatar
  • 167
1 vote
1 answer
125 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 ...
Noob's user avatar
  • 23
1 vote
1 answer
100 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,...
Ghost-of-PPPF's user avatar
9 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 ...
Liren Lin's user avatar
  • 191