Shots and Circuit Repetitions: Developing the Expectation Value for Results from a Quantum Computer

  1. Motivation
  2. The problem
  3. Two forms of uncertainty in a quantum computer
  4. Statistics to the rescue
  5. Statistical aggregation to develop the expectation value
  6. How does a classical computer avoid the inherent probabilistic nature of quantum mechanics?
  7. Apparent determinism = probability + statistics
  8. Stochastic processes
  9. Quantum computing seeks to exploit the inherent uncertainty of quantum mechanics
  10. Everything is fine, until you measure qubits
  11. Applying statistics to measurement
  12. Don’t forget the noise and errors
  13. Environmental interference
  14. Noise vs. errors vs. environmental interference
  15. Measurement errors
  16. Each qubit has its own noise and error profile
  17. Shot count, shots, or circuit repetitions
  18. How many shots or circuit repetitions are needed?
  19. You need to know what results to expect
  20. Expectation value
  21. Simplified concept of expectation value
  22. Raw quantum results
  23. Bit string cases
  24. Quantum registers
  25. Cases of series of results
  26. Possibility of garbage results
  27. What to do about outliers
  28. Actual vs. requested shot count
  29. What to do when there is no clear dominant result
  30. Just take the average of the results — or the most common result
  31. Manually examine all results
  32. What fraction of shots should be dedicated to probabilistic nature vs. noise?
  33. Testing to characterize effects of noise, errors, and environmental interference on results
  34. Four types of dynamic shot count
  35. Dynamic shot count based on parameters
  36. Automatic dynamic shot count?
  37. Won’t quantum error correction solve the problem?
  38. Wall clock time
  39. Context of a quantum simulator
  40. Design for portability
  41. Is 10 ever a reasonable shot count?
  42. IBM Qiskit default shots is 1024
  43. Is 100 shots reasonable?
  44. What is the maximum shots for a single circuit?
  45. No clear rules, methodology, or guidance for shot count
  46. What’s a good design goal for shot count when designing new algorithms?
  47. Rules of thumb for shot count
  48. Formulas for shot count
  49. Intuitions for shot count
  50. Need to balance shot count and wall clock time
  51. How many digits of precision are reasonable?
  52. How does precision affect shot count?
  53. Is it still too soon to worry too much about shot counts?
  54. One exception: true random number generation — only a single shot required
  55. Don’t confuse circuit repetitions with the iterations or layers of variational methods
  56. Don’t confuse circuit repetitions with experiments
  57. Iterations of variational algorithms
  58. Application experiments
  59. Watch out for total circuit executions
  60. Don’t get too used to the nuances and glitches of the quantum machine you used yesterday
  61. How does quantum volume impact shot count?
  62. What is the impact of shots on quantum advantage?
  63. What about quantum supremacy?
  64. Scaling shot count for Shor’s algorithm
  65. Advice to authors of papers on quantum algorithms
  66. Recommendations
  67. Conclusions
  68. What’s next?

Motivation

As I was reading various academic papers on quantum computing algorithms in recent months it occurred to me that the matter of specifying a value for shot count (circuit repetitions) for execution of a quantum circuit seems a rather vague area. I’ve seen nothing in the way of…

  1. Formal — or even informal — treatment of the question of how to determine how many shots (circuit repetitions) are appropriate for a particular quantum circuit.
  2. Any consistency in focus on the importance of shot count.
  3. How shot count should scale as the input data scales.
  4. How exactly specific changes in error rates and coherence times should impact shot count.
  5. Limitations of increasing shot count — at what point can you simply not get a statistically valid result from a quantum circuit due either to the nature of the circuit itself (probability) or the quantum hardware being too noisy.
  6. How to analyze a circuit to determine an optimum shot count.
  7. Formal formulas for computing shot count.
  8. Even informal rules of thumb for estimating shot count.
  9. Robust guidance for when the vendor default for shot count — or 100 or 1,000 — fails to deliver satisfactory results, what should the algorithm or application designer do — in a more methodical manner rather than a haphazard trial and error manner.
  10. Could shot count be computed or estimated automatically based on circuit and some statement on required precision and any wall clock time limit? IOW, parameters which the application developer is likely to know and understand.
  11. How exactly an application developer who needs a deterministic value should treat the probabilistic results from a quantum calculation. What statistical techniques can or should be used to derive an expectation value?
  12. How to tune shot count based on desired precision of expectation value.
  13. How extreme shot count requirements might impact quantum advantage. For real-world scenarios.

The problem

In short, the entire problem is the simple fact that unlike classical computers, quantum computers are inherently incapable of strict determinism — 2 + 2 is not always 4. Most of the time it is, maybe, but no guarantees, and much of the time it won’t necessarily be. The best we can say with a quantum computer is that 2 + 2 will likely be 4, but not always.

Two forms of uncertainty in a quantum computer

The outcome of the execution of a quantum circuit — the measurement of the results of a quantum computation is impacted by two forms of uncertainty:

  1. The inherent probabilistic nature of quantum computers and indeed of quantum mechanics itself.
  2. Noise and errors due to our inability to construct an ideal, perfect quantum computer at this time — noise and errors in the physical components as well as environmental interference from outside of the quantum computer that we are currently unable to filter out well enough to prevent the sensitive components of the quantum computer from being affected. This includes decoherence as well — the quantum state of a qubit will decay over time.

Statistics to the rescue

That sounds like a huge, insurmountable problem, but actually it isn’t.

Statistical aggregation to develop the expectation value

It’s not statistics per se that solves the problem, but statistical aggregation that does the trick.

How does a classical computer avoid the inherent probabilistic nature of quantum mechanics?

If everything — EVERYTHING — is based on quantum mechanics, how is it that classical computers can be strictly deterministic? For that matter, how can anything ever be stable and certain?

Apparent determinism = probability + statistics

So, even though quantum computers are not inherently deterministic in the same way as classical computers we can achieve apparent determinism at the classical application level by applying statistics (statistical aggregation) to the raw probabilistic values produced by the raw quantum hardware. That’s an interesting and useful division of labor.

Stochastic processes

A stochastic process is simply any system whose output or state appears random, to some degree, meaning it is not strictly deterministic or predictable. At best you can conjecture a range of values or particular values with some probability. Personally, I say that such a system is probabilistic, but it’s the same concept — a stochastic process or a stochastic system. Stochasticity is the more formal mathematical term for the overall process which I simply refer to here as probabilistic.

Quantum computing seeks to exploit the inherent uncertainty of quantum mechanics

What makes a quantum computer so different, despite all of the advanced technology that it uses — including a lot of advanced classical electrical circuits — is that the whole point of quantum computing is to exploit the probabilistic nature of quantum mechanics.

Everything is fine, until you measure qubits

It is only when we seek to read or measure that state of a qubit that we run into this issue of the probabilistic nature of quantum state. The probability amplitudes for the binary 0 and 1 as well as the phase cannot be read or measured directly and independently. The measurement operation is inherently classical, producing either a binary 0 or a binary 1 bit value for each measured qubit regardless of the complexity of its quantum state.

Applying statistics to measurement

You can run your quantum circuit which results in a 0.25 (or 0.75) probability of binary 1 and sometimes it gives you a binary 1 but other times you get a binary 0. It all seems so… random.

Don’t forget the noise and errors

Even if you have carefully pre-calculated the expected probabilities for binary 0 and 1, we still have the significant potential for noise and errors in the hardware and environment which can cause measurements to vary a little, somewhat, or even dramatically from the quantum state expected on an ideal quantum computer.

Environmental interference

Some of the noise and errors in quantum computations come directly from the quantum hardware, the qubits themselves and the circuitry which connects and controls them. As time goes on, hardware engineers will come up with increasingly more sophisticated hardware designs and implementations which reduce such noise and errors, but even if they were to produce perfect hardware, noise and errors can come from an external source: so-called environmental interference.

Noise vs. errors vs. environmental interference

From the perspective of an algorithm designer or application designer, noise, errors, and environmental interference are all the same thing and all have the same effect — sometimes a qubit which should measure as a 1 measures as a 0 and sometimes a qubit which should measure as a 0 measures as a 1.

  1. Noise differs from environmental interference in that the source of the noise is within the quantum computer itself — from electrical, electronic, and mechanical components, cabling, wiring, circuit connections, and intermittent interactions of any of the preceding, while environmental interference by definition has a source external to the quantum computer (see the preceding section.)
  2. Errors can be caused by noise and environmental interference, but errors are generally caused by the flawed execution of operations, such as quantum logic gates and measurement operations (so-called measurement errors), as well as decoherence. An operation on one qubit can also have an unintended effect on a nearby qubit — so-called spectator errors or crosstalk. Microwave signals and laser operations simply aren’t 100% foolproof, yet.
  3. Even if there were no environmental interference, no noise within the quantum computer, and all operations are executed flawlessly, there is still the possibility of errors as a result of decoherence, where an idle qubit gradually decays from a 0 to a 1 or from a 1 to a 0.

Measurement errors

As disappointing as it is that basic qubit operations can and frequently fail to be executed properly, it’s actually quite shocking to find out that the simple act of measuring a qubit is not 100% reliable. Granted, the measurement error may be relatively small, but it will show up if you execute your quantum circuit enough times.

Each qubit has its own noise and error profile

You might think that every qubit of a machine would be identical and behave identically — as bits in a classical computer do — but that’s not the case, at least with current quantum technology. Each qubit will have its own noise and error rate, as well as its own decoherence time.

Shot count, shots, or circuit repetitions

The number of times we decide to run the same exact quantum circuit is called circuit repetitions or sometimes shots or shot count.

How many shots or circuit repetitions are needed?

Based on knowledge of your quantum circuit you should be able to calculate, estimate or at least guess what range of probability you are dealing with and adjust your shots or circuit repetitions accordingly. Is your circuit more like flipping a coin, rolling dice, or picking a card from a shuffled deck of cards.

  1. Increase the number of shots or circuit repetitions until you get statistically accurate results that you are comfortable with.
  2. Reduce the number of shots or circuit repetitions until the total wall clock run time is acceptable for your needs while still producing statistically accurate results that you are comfortable with. It’s a balancing act and tradeoff between the two competing interests.

You need to know what results to expect

This trial and error approach to determining an optimal number of shots or circuit repetitions presumes that you know what results to expect. Begging the question of what to do if you don’t know the expected results in advance, where does the expected result come from?

Expectation value

If you take a number of measurements of some physical phenomenon — what physicists in quantum mechanics call an observable — they will likely not all be identical, but we’d like to characterize them as if they were one number. The common way of doing that is a simple average — add up the numbers and divide by the count of numbers being summed. Statisticians call this average the mean of the series of numbers. They have a fancier name for it as well — expectation value or simply expected value.

  1. https://en.wikipedia.org/wiki/Expectation_value_(quantum_mechanics)
  2. https://en.wikipedia.org/wiki/Expected_value
  3. https://mathworld.wolfram.com/ExpectationValue.html
  1. A single qubit whose value will be a binary 0 or 1. An average of 0.5 is not terribly useful when measuring qubits.
  2. A physical phenomenon such as energy levels of electrons, which are discrete levels rather than a continuous range of real numbers.
  3. A range of integers. A real, non-integer average is not very useful.
  4. A collection of bit strings — one bit per qubit, one bit string for each computational basis state. Each value is a pattern. A numerical average is not useful.

Simplified concept of expectation value

Not having any desire to get bogged down in the finer points of physics or mathematics, for the purposes of this informal paper, I’ve adopted a simplified conception of expectation value. It has two parts:

  1. What are the expectations about what a single value (single measurement) looks like. Such as its range of possible values and the theoretical distribution of those values, possibly even a probability for each value. That’s in line for the quantum mechanical notion of expectation value.
  2. How do we want to think about a series of measurements. What information do we want to extract from the series?

Raw quantum results

A quantum computation — the execution of a quantum circuit — can produce results or output by the measurement of one or more qubits, possibly all of the qubits.

  1. A single qubit. A binary bit 0 or 1, or a boolean value false or true.
  2. A collection of single qubits considered as a group, a bit string, but each still a discrete binary value, typically potentially entangled, such as a so-called register, interpreted as a raw bit string but not interpreted as a single binary integer. For example, the two qubits of a Bell state, or three or more qubits in a GHZ or W state.
  3. A collection of qubits which represent the binary digits of an integer. Two bits for 0–3, three bits for 0–7, four bits for 0–15, 10 bits for 0–1023, and so on.
  4. A collection of qubits which represent the fractional binary digits of a binary point number, from 0 to 0.999… (up to by not including 1.0.) Two bits for 0, 0.25, 0.50, and 0.75. Three bits for 0 to 0.875. Four bits for 0.9375. And so on.
  5. Some combination of any number of the above — zero or more individual qubits, zero or more bit strings, zero or more k-bit integers, and zero or more k-bit binary-point fractions. Where each number may have its own value of k.

Bit string cases

Here are the cases of bit string results for quantum circuits which I am aware of:

  1. All bits independent, isolated, uncorrelated.
  2. 2-qubit Bell states — correlation or dependency between the quantum state of the two qubits.
  3. k-qubit GHZ state — all 0 or all 1, in theory.
  4. k-qubit W state — exactly one bit is 1, rest are 0, in theory.
  5. k-bit integer.
  6. k-bit binary fraction.

Quantum registers

Quantum computers don’t have registers in the same sense as for a classical computer, but a quantum algorithm or quantum application can nonetheless interpret a collection of otherwise independent qubits as if they actually were a classical-style register, such as for bit strings or integer numbers.

Cases of series of results

When a quantum circuit is executed repeatedly a table of results is effectively generated. Think of each circuit execution as producing one row in the table with each of the columns of a row containing the results for that one column for that one circuit execution.

  1. The raw values across all rows. Let the application sort them out.
  2. Exclude duplicates from raw values.
  3. The simple integer arithmetic average of a column across all rows. Simply add the column across all rows and divide by the number of rows.
  4. Exclude outliers from the simple integer arithmetic average. Specify count or threshold for outliers, smallest and largest values. Alternatively, outliers could be based on low-frequency integer values.
  5. Maximum value. What is the largest value which occurs across all rows for a given column.
  6. Most frequent value. Which binary value occurs most frequently across all rows for that column.
  7. Top k values. May be identical.
  8. Top k most common values. Ignoring duplicates.
  9. Cutoff threshold. How many values (rows) have a value in the column with a binary value above a specified binary value.
  10. Cutoff threshold average. Average of all of the values above the cutoff threshold.
  11. Bit string distribution. Frequency distribution for each unique bit string value from 0…0 to 1…1 for the number of qubits in the bit string. Generally only useful for relatively short bit strings since there will be 2^k entries, which is one million even for k of 20. Although, just because there are potentially 2^k entries, that doesn’t mean that every value is captured — the values may be relatively sparse. But even then, if your shot count is high and there is lots of noise and errors, many spurious values could be generated.
  12. Raw distribution. Counts for each unique value.
  13. Bucket distribution. Divide the k-bit values into some number of buckets and return a count or percentage of the row values which fall into each bucket.
  14. Maximum bucket. Simply the bounds of the bucket (or bucket number) which contains the most values. Which raw value occurred the most in that bucket. Should have the option of raw count of values in a bucket or a percentage, fraction, or probability based on the shot count.
  15. Bimodal distribution. Return the central value for each of the two peaks of a bimodal distribution, and possibly the number of values occurring within a range about the peaks.
  16. Multiple peaks. Return a list of all peaks, with a minimum distance between peaks. Optionally order the peaks by number of number of rows at the peak value or within some minimum distance from the peak value.
  17. Period of the peaks. Measure the distance between peaks. Or distances plural.
  18. Random. No apparent true, single value or pattern.
  19. Garbage. Not truly random, but no discernible value or pattern.
  1. Raw counts.
  2. Fractions.
  1. Were there more 1’s than 0’s — true or false.
  2. What percentage of the time was the result a 1. How close to 100%? Well above 50% or close to 50%?
  3. How random did the sequence appear? Longest run of 1’s or 0’s. Average percentage of time with runs of 1’s or 0’s longer than some threshold, say 3 or 4. Other measures of randomness.
  4. Raw binary values. Such as simply generating random bit values.

Possibility of garbage results

If the values across rows appear to be garbage or random, the classical application should consider abandoning the experiment and possibly raising an application error that no coherent result could be achieved — using the designated number of circuit repetitions.

What to do about outliers

Given the variability of results of quantum computations subject to probability, noise, and errors, it will be no surprise that outliers — values well beyond a range to be expected — will crop up with some frequency. The question is what to do about them. Some approaches:

  1. Accept them as is. If the shot count is high enough, they may simply get washed away in the statistical aggregation.
  2. Ignore them. Based on some numeric threshold, values which are too far outside an expected range could simply be dropped.
  3. Ignore the fringe values — highs and lows. Regardless of any expected range, simply drop a percentage of the highest and lowest values.

Actual vs. requested shot count

The backend software for your requested quantum computer may not exactly honor your requested shot count. For example, the backend may have a maximum which is less than the requested shot count.

What to do when there is no clear dominant result

There’s clearly a lot of potential complexity in handling the results across all circuit repetitions. The variability might get way out of hand, so that a handful of statistical tricks simply don’t winnow the results down to a nice clean single dominant expectation value.

Just take the average of the results — or the most common result

In other cases, consider just accepting the variability and simply average the values returned by each circuit execution. All of the noise and errors may simply cancel out or at least partially cancel out.

Manually examine all results

Although the goal is fully automatic handling of results to obtain a deterministic expectation value, it can be helpful to manually examine all (or at least some) of the raw results of a quantum computation since:

  1. There may be unexpected surprises.
  2. There may be some strange biases.
  3. There may be some anomalous results which should be discarded as outliers.
  4. There may be bimodal or multimodal results rather than a single peak — or vice versa.
  5. Your preconceptions and intuitions about what the results should look like may be a little bit off, skewed somewhat, or just plain completely wrong.

What fraction of shots should be dedicated to probabilistic nature vs. noise?

There may not be any definitive method to determine how many shots are needed to compensate for the probabilistic nature of quantum computing vs. noise, errors, and environmental interference.

Testing to characterize effects of noise, errors, and environmental interference on results

Even if you have solid specifications characterizing your quantum computer, it is still highly advisable for the algorithm and application designers to run some comprehensive and serious tests to determine the degree to which noise, errors, and environmental interference are actually impacting the results of a quantum computation. There could be surprises — some good, some bad, some great, some really ugly. Some issues to look out for:

  1. Are there any obvious patterns?
  2. Are there test cases which just give really bad results?
  3. Are there test cases which surprisingly give much better than expected results?
  4. Are all of your assumptions born out?
  5. Do you see things that you really didn’t expect?
  6. How do the test results affect how you conceptualize the expectation value for the quantum computation?

Four types of dynamic shot count

Rather than being fixed or a user input, the classical application code which invokes a quantum circuit can calculate an approximate value for shot count.

  1. Dependence on particular input data and parameter values. Particularly where the quantum circuit itself is dynamically generated based on the input data and parameters.
  2. Portability — to significantly or even somewhat different hardware.
  3. Calibration settings for the particular machine at the particular moment. Calibration can drift as well.
  4. Individual qubits or particular combinations of qubits can have distinct noise and error rates and coherence times.

Dynamic shot count based on parameters

If a quantum algorithm (circuit) is dynamically generated by classical code based on the input data and various parameters, then the shot count (circuit repetitions) likely needs to be dynamically calculated as well. Some experimentation may be necessary (probably, maybe absolutely certainly) to derive an approximate formula for computing the shot count.

  • 5,000, 25,000, 125,000, and 625,000
  • 10,000, 100,000, 1,000,000, and 10,000,000

Automatic dynamic shot count?

This isn’t practical today, but conceivably on some future quantum computer architecture it might be feasible to support a dynamic shot count which stops repeating the quantum circuit after it seems that the result values have converged within some relatively narrow range.

Won’t quantum error correction solve the problem?

Quantum error correction (QEC) will indeed be a giant leap forward for quantum computing — when or even if it happens, but it won’t be happening any time soon, so for now and the next 2–5 years we have to make do with non-corrected NISQ machines.

Wall clock time

Sure, computers are generally very fast, executing many individual operations in a tiny fraction of a second, but if you have to repeat those operations many, many times — hundreds, thousands, and even millions of times, those fast operations suddenly take far more than a tiny fraction of a second. That, coupled with the possible needs of the application to execute a significant number of circuits, such as for variational methods, and suddenly you may be looking at macroscopic time — many seconds, minutes, even hours, possibly well beyond external requirements which may need results in less time than that.

Context of a quantum simulator

Generally a quantum simulator can be expected to model an ideal, perfect quantum computer which is probabilistic but with no noise, errors, or environmental interference, provided that the number of qubits is small enough to practically simulate 2^n quantum states on a real classical computer system. Currently that’s somewhere in the 2⁴⁰ to 2⁵⁵ range of quantum states (40 to 55 qubits) in theory, but much smaller from a practical perspective. But it’s also possible or even desirable to enhance the simulator with noise and error models to simulate not an ideal, perfect quantum computer, but actual, real, current quantum computers or machines which might be practical in the coming years.

  1. Shot count needed to achieve a desired precision of results based on a modeled degree of noise and errors.
  2. Degree of modeled noise and errors required to achieve the desired precision of results for a particular shot count.
  1. Predict what improvements would be needed in real hardware to achieve the desired precision and shot counts.
  2. Calculate or adjust shot count based on measured level of noise and errors on a particular machine. Real machines are periodically recalibrated and the calibration can vary over time.

Design for portability

It is worth noting that generally we shouldn’t be trying to design algorithms which only run on a particular machine — portability is highly desirable. The ability to run a given algorithm on a wide range of quantum computers is a highly desirable characteristic. The shot count is likely to vary widely across machines. There may be a single shot count which runs across all possible machines, but it may be a real waste of resources on machines which are more capable.

Is 10 ever a reasonable shot count?

For toy algorithms or mere experimentation with only a handful of quantum logic gates, 10 might actually be a reasonable shot count.

IBM Qiskit default shots is 1024

As of the time of this writing (July 4, 2020), IBM Qiskit defaults to 1024 shots for the qiskit.execute function, unless the max_shots backend configuration parameter is less than 1024, in which case the lower number is used.

Is 100 shots reasonable?

For most casual work with quantum algorithms, 100 shots may well be quite reasonable — much better than 10 and much less resources than 1,000.

What is the maximum shots for a single circuit?

Each machine probably has a maximum number of shots or circuit repetitions which are supported.

No clear rules, methodology, or guidance for shot count

As far as I can tell, there are simply no clear rules, methodology, or guidance for calculating the appropriate number of shots for a given quantum algorithm or application.

What’s a good design goal for shot count when designing new algorithms?

Unfortunately, there is no good answer to the question of what shot count designers of new algorithms should have in mind as a goal or target for their new quantum algorithm.

Rules of thumb for shot count

Sorry, but to the best of my knowledge there are not any rules of thumb or trivial formulas yet for estimating shot count.

Formulas for shot count

Again, sorry, but to the best of my knowledge there are not yet any crisp, magic formulas, simple, complex, or otherwise, for estimating shot count.

Intuitions for shot count

Once again, sorry that there are still no coherent, clear intuitions for how to estimate shot count for an algorithm or application.

Need to balance shot count and wall clock time

It’s easy to raise the shot count in pursuit of greater precision, but that raises wall clock time, which could become problematic, especially if a lot of experiments must be run. So there’s a tension or at least a possibility of a tension.

How many digits of precision are reasonable?

We’ve all been spoiled by the determinism and precision of classical computers. Single precision math generally has more precision than most applications need. If that’s not enough, there is double precision. And if that’s not enough there is extended precision, and even quad precision. And if even that’s not enough, there are packages which provide arbitrary precision.

How does precision affect shot count?

Unfortunately, there is no magic formula or rule of thumb for calculating or estimating shot count given a desired number of digits of precision for a measured quantum result. For specific niche classes of algorithms you may well be able to come up with a formula or rule of thumb, but for the general case, the best you can do is experiment and trial and error.

Is it still too soon to worry too much about shot counts?

Is the input data for a typical quantum algorithm too small and the algorithms too simple for shot count to statistically be a major issue? If so, a hardwired 100 or 1024 default may indeed be good enough, for now.

One exception: true random number generation — only a single shot required

In most cases the classical code invoking a quantum circuit is attempting to achieve a significant degree of determinism, but there is one notable exception: generation of true random numbers.

Don’t confuse circuit repetitions with the iterations or layers of variational methods

The iterations of the classical code of a variational algorithm are usually referred to as the outer loop. Each iteration of the outer loop will in turn invoke the quantum circuit a number of times. Shot count and circuit repetitions refer to those invocations of the quantum circuit, within the outer loop.

Don’t confuse circuit repetitions with experiments

A quantum application may conduct a number of experiments, typically with distinct parameters for each experiment. Each experiment will then invoke a quantum circuit a number of times. Shot count and circuit repetitions refer to those invocations of the quantum circuit, not the overall number of experiments.

Iterations of variational algorithms

Hybrid quantum/classical algorithms are quite popular these days, especially since NISQ machines are not capable of executing deep quantum circuits. The common use case is algorithms based on variational algorithms (variational method.) The impact of this is that the classical portion of the algorithm will execute some number of iterations, with each iteration invoking the classical circuit. Each of those iterations will then need a shot count to execute the quantum circuit a designated number of times or circuit repetitions.

Application experiments

On top of the iterations in a variational algorithm, there may be another level of application logic which invokes the variational algorithm some number of times with variations of input data and parameters. So then we have three levels of counts:

  • Number of application experiments.
  • Number of iterations within each experiment.
  • Shot count for each quantum circuit invocation within each iteration.

Watch out for total circuit executions

The total number of quantum circuit executions will be the product of the number of experiments and the number of circuit repetitions, with the caveat that circuit repetitions might vary from experiment to experiment if dependent on the parameters of the experiment.

Don’t get too used to the nuances and glitches of the quantum machine you used yesterday

It’s far too easy to learn all of the nuances and glitches of the machines and software that you use on a regular basis. It’s tempting and natural to distort and adapt your thought processes, algorithms, and code to work with and around those nuances and glitches. And that can work quite well — until it doesn’t.

How does quantum volume impact shot count?

IBM’s notion of quantum volume (formal paper) incorporates noise, errors, and environmental interference as well as number of qubits and connectivity, so an increase (or decrease) in quantum volume for the same number of qubits would seem to suggest that fewer (or more) shots might be needed for a given quantum circuit.

What is the impact of shots on quantum advantage?

How do shot counts scale as the input grows and does that maintain or increase any actual quantum advantage or reduce it?

What about quantum supremacy?

Technically, when quantum supremacy is achieved, by definition we are getting results which we can’t predict using classical computing, in which case we will have no way to tell whether we have enough shots or not. Interesting problem!

Scaling shot count for Shor’s algorithm

There has been a lot of hype about Shor’s algorithm for factoring large semiprime numbers, but as far as I can tell none of the formal treatments have provided any robust analysis of how shot count would need to scale as the input size grows.

Advice to authors of papers on quantum algorithms

My primary advice to the authors of formal papers on quantum algorithms is simply to give more attention to shot counts:

  1. Always be explicit about what shot count was needed or recommended.
  2. Be clear about the technical justification behind any shot count.
  3. Provide a solid mathematical formula whenever possible.
  4. Offer a crisp rule of thumb whenever possible.
  5. Preferably give a treatment for how shot count would scale as input grows.
  6. At least speculate what might need to happen for shot count as input grows.
  7. Consider and separate discussion of shot count for an ideal quantum simulator, an at least partially noisy quantum simulator, a current NISQ device, and speculation about better NISQ devices which may be available within 1–2 years.
  8. How shot count might impact quantum advantage. Especially when a very large shot count is needed.

Recommendations

  1. If all you are doing is very trivial demonstrations and relatively minor experiments, you can probably get by using the default setting for shot count. The only really important thing to bear in mind is that generally a quantum computation will be probabilistic and will not produce a single deterministic result, but a frequency distribution from which some inference must be made as to the likely result, or results plural, or range of likely results.
  2. Plan to run experiments to see how sensitive your results are to variations in circuit repetitions.
  3. Reflect on how shot count will, might, or could scale as input size or output precision grows.
  4. If you are authoring a formal or academic paper, please say something explicit about shot counts, how you determined them, how you validated them experimentally, and how they might scale with input size — see the preceding section.

Conclusions

It may still be too soon to worry too much about tuning and scaling of shot count (circuit repetitions), but that may simply mean that we have much further to go to achieve algorithms and applications that are ready for prime time with clear and dramatic quantum advantage.

What’s next?

I’ll be continuing to monitor progress of research, implementation, and practice for the quantum computing sector, such as:

  1. Development of formulas and methods for explicitly calculating shots and circuit repetitions for particular quantum circuits.
  2. Development of less flawed and less noisy qubits. Less noise and fewer errors — mean fewer shots are needed to compensate for them.
  3. Development of quantum computers better shielded from environmental interference.
  4. Improvements in coherence time of qubits. And how that impacts required shot count.
  5. Development of quantum algorithm techniques that can reduce circuit length and hence cumulative errors.
  6. Development of quantum algorithm techniques which can mitigate noise and errors within the quantum circuit, reducing the need for extra shots.

--

--

Freelance Consultant

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store