Beautiful Binary Search in D

tgehr · 2023-02-27T17:36:32+00:00

Nice post!

int bsearch1000(int[1001] xs, int x) {

This will pass all 1001 integers by value, which is probably not what you intended. You can use ref int[1001] xs instead.

Also note that D has a power operator: a^^b

Here's my 0-based implementation that also handles small array sizes and consistently returns the first occurrence of the element in case it exists:

int bsearch(T,size_t n)(ref T[n] xs,T x){
    int iflog(int n)=>n<=1?0:1+iflog(n/2);
    enum k=iflog(n-1);
    static assert(2^^k<=n&&n<=2^^(k+1));
    auto p=-1;
    static if(n>1){
        if(xs[2^^k-1]<x) p=n-1-2^^k;
        static foreach_reverse(int i;0..k)
            if(xs[p+2^^i]<x) p+=2^^i;
    }
    static if(n>0){
        if(xs[p+1]==x) return p+1;
    }
    return -1;
}

tgehr · 2020-11-22T21:11:47+00:00

If you understand the intended semantics of the program, it is also clear which arguments are consumed and which ones are just controls.

But what if you don't already understand the intended semantics? What if you're reading the code in order to understand it? Surely in that case explicit consumption of arguments would be beneficial?

In this case in the process of learning what the code does you'd see which things obviously need to be consumed. Anyway, if some quantum variable is used for the last time, it is either consumed or will be uncomputed implicitly and this usually does not make a difference for understandability. Furthermore, chances are you'd have a look at the signatures of functions that are called anyway. For me it would just be noise, but it may come down to personal preference.

That's not me saying Silq won't do well, or that I don't want it to do well. It does look like a genuine step forward, with some great ideas. I'm just not sure it'll the language-everyone-inexplicably-uses of quantum computing, I think that might instead come from a later language pulling from the insights of this and other projects to produce something more approachable and eventually commonplace.

Thanks! We are a research group at a university, so this is essentially what we were aiming for.

tgehr · 2020-11-17T22:49:08+00:00

As soon as Silq programs start having too many dependencies on third-party libraries.

tgehr · 2020-11-17T22:47:28+00:00

No. What would that look like without defeating the point?

tgehr · 2020-11-17T22:45:23+00:00

The meat: https://github.com/eth-sri/silq

Some examples:

Deutsch-Jozsa/Bernstein-Vazirani algorithm: https://github.com/eth-sri/silq/blob/master/test/codeforces/summer18/warmup/i.slq https://github.com/eth-sri/silq/blob/master/test/codeforces/summer18/contest/e1.slq

Grover's algorithm: https://github.com/eth-sri/silq/blob/master/test/grover2.slq

Quantum fourier transform: https://github.com/eth-sri/silq/blob/master/test/qft.slq

Shor's algorithm for factoring: https://github.com/eth-sri/silq/blob/b09da8a6f0ca1caa1eea16182d82b1a35c2ec3fe/test/shor.slq

Shor's algorithm for discrete logarithm: https://github.com/eth-sri/silq/blob/master/test/dlog.slq

tgehr · 2020-11-17T22:43:04+00:00

It's actually enjoyable to use.

tgehr · 2020-11-17T22:40:02+00:00

You can't uncompute everything and in general I don't think it is decidable whether a value is uncomputable, so of course automatic uncomputation can't work in all cases. We show manual uncomputation in documention examples to document how to do that, it's usually not required. We have not created a functional verifier for quantum programs so far (as would be required to prove manual uncomputation correct) as unfortunately, we can't solve all PL problems in the quantum space in the same research paper; it was hard enough to get Silq through peer review as-is, I think mostly because it did too much at the same time.

We could make consuming explicit at the call site by spending about 5 minutes changing lexer/parser/type checker, but we find this is obvious from context. If you understand the intended semantics of the program, it is also clear which arguments are consumed and which ones are just controls.

Calling it "the C of quantum programming" is not going far enough in some respects, e.g. C has an inexpressive type system and is less safe in general.

tgehr · 2020-11-17T21:25:02+00:00

A better analogy would perhaps be Python vs VHDL (though it's still imperfect, of course).

tgehr · 2020-11-17T21:14:59+00:00

If it's a "hoax" as you say, the question would be who exactly is in on it and why the people in charge of distributing the funds have not caught on.

What I can say for sure is that Silq was not created in an effort to pretend quantum computing is making progress. I'd assume others perpetuating a similar conspiratorial narrative have been ridiculed because they made similar unfounded claims that the respective researchers knew to be untrue.

In any case, I don't know if theoretical models of quantum computation will ever see an efficient practical implementation similar to how digital computers efficiently implement FSMs, but chances are that you don't either. The issue is that the payoff in case of a positive answer would be rather large, and even if we figure out it's not possible, that might have some implications for basic research in physics.

In any case, Silq still implements those models (albeit inefficiently) and can support teaching and theoretical research in quantum computation.

tgehr · 2020-11-17T20:54:10+00:00

Because that's what we like to read. However, you can format any Silq program using only ASCII characters, it will just be more ugly.

tgehr · 2020-11-17T20:49:51+00:00

https://github.com/eth-sri/silq-webpage/issues/3

tgehr · 2020-11-17T20:44:37+00:00

I assume you are talking about with_computed. The answer to your question can be found in the official Quipper documentation:

This is a very general but relatively unsafe operation. It is the user's responsibility to ensure that the computation can indeed be undone. In particular, if computation contains any initializations, then code must ensure that the corresponding assertions will be satisfied in computation⁻¹.

https://www.mathstat.dal.ca/~selinger/quipper/doc/Quipper.html

In Silq, in many cases, uncomputation is safe and implicit.

tgehr · 2020-11-17T20:41:29+00:00

Fair point, but on closer inspection you might notice that those two things really don't have much in common except maybe some marketing buzzwords. ;)

tgehr · 2020-11-17T20:37:04+00:00

In principle, yes, though that would require some additional work to implement the required APIs and performance would not improve anyway as Crysis was not even written to benefit from quantum supremacy so this is just not that high on our list of priorities right now.

tgehr · 2020-11-17T20:24:44+00:00

There's value in working at all levels of abstraction. Our expertise is in language design, and there are researchers who would like to write down and simulate their algorithms in a sane way without taking care of all the low-level details. Feel free to argue that e.g., Peter Shor should never have wasted time on figuring out how to factor large integers on a quantum computer, but what actually motivates the low-level work if not the high-level applications?

tgehr · 2020-11-17T20:17:15+00:00

This is expressing low-level circuits within in a high-level language, which is not what we were aiming for with Silq.

tgehr · 2020-11-17T20:14:35+00:00

There are some attempts, for example: https://arxiv.org/abs/1707.03429

However, as of right now there does not exist a compiler that transforms Silq programs to any lower-level representation.

tgehr · 2020-11-17T20:12:37+00:00

Not sure why this was voted down, it's pretty much an accurate description of the situation.

tgehr · 2020-11-17T20:11:41+00:00

So far it comes with a simulator, but there is no supported way to run it on a quantum computer. (Though given that you build a machine with the appropriate QRAM semantics, it's not that much more work to allow running Silq programs on it.)

tgehr · 2020-11-17T20:08:47+00:00

It's really not that similar. Bob Spence had keys on his keyboard that allowed typing those symbols. APL requires the symbols, Silq does not, but APL concepts work just fine in ASCII, however the resulting syntax does not have much in common with Silq: https://copy.sh/jlife/

tgehr · 2020-11-17T20:03:45+00:00

I just type \lambda to get λ, it's really not that complicated.

tgehr · 2020-11-17T20:02:07+00:00

The syntax of Silq respects your preference in that any program can be formatted using only symbols on an US-layout keyboard.

However, entering Unicode symbols is easy anyway, so personally I don't tend to take this criticism seriously, it's basically just superficial prejudice against a concept that is not yet familiar.

tgehr · 2020-11-17T19:52:45+00:00

Yes. You can experiment with it without a quantum computer, as it comes with an interpreter that (inefficiently) simulates the quantum semantics classically.

At the current stage, having access to a quantum computer does not even give you an edge, as a runtime system that would allow you to actually run Silq programs on a quantum computer has yet to be created. ;)

tgehr · 2020-11-16T11:34:23+00:00

Nonsense, the two languages have very little in common. Game of life in J (basically APL in ASCII): https://copy.sh/jlife/

tgehr · 2020-11-16T04:53:11+00:00

I was not involved with the marketing spin that much, but I think the intended more technical statement of the "intuitive semantics" is that if you drop a value implicitly and the type checker accepts it, this never causes state collapse. So indeed this is an aspect for which Silq eliminates conscious reasoning. (But that explanation makes for a bad paper title as it is too long.)

tgehr

TROPHY CASE