Diego Arroyuelo
email: darroyue@inf.utfsm.cl

Rodrigo Cánovas

Gonzalo Navarro
email: gnavarro@dcc.uchile.cl

Rajeev Raman
email: r.raman@mcs.le.ac.uk

LZ78 Compression in Low Main Memory Space

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The Ziv-Lempel algorithm of 1978 [START_REF] Ziv | Compression of individual sequences via variable length coding[END_REF] (known as LZ78) is one of the most famous compression algorithms. Its variants (especially LZW [START_REF] Welch | A technique for high performance data compression[END_REF]) are used in software like Unix's Compress and formats like GIF. Compared to the stronger LZ77 format [START_REF] Ziv | A universal algorithm for sequential data compression[END_REF], LZ78 has a more regular structure, which has made it the preferred choice for compressed sequence representations supporting optimaltime access [START_REF] Sadakane | Squeezing succinct data structures into entropy bounds[END_REF] and compressed text indexes for pattern matching [START_REF] Ferragina | Indexing compressed texts[END_REF][START_REF] Russo | A compressed self-index using a Ziv-Lempel dictionary[END_REF][START_REF] Arroyuelo | Stronger Lempel-Ziv based compressed text indexing[END_REF] and document retrieval [START_REF] Ferrada | A Lempel-Ziv compressed structure for document listing[END_REF][START_REF] Ferrada | Efficient compressed indexing for approximate top-k string retrieval[END_REF].

Compared to LZ77, the LZ78 compressed output is also easier to build. For example, a simple and classical implementation compresses a text of length n over an alphabet [1..σ] into z integers, where √ n ≤ z = O(n/ lg σ n), in O(n lg σ) deterministic or O(n) randomized time, using O(z lg n) = O(n lg σ) bits of space. A comparable result for LZ77 was obtained only recently [START_REF] Köppl | Lempel-Ziv computation in compressed space (LZ-CICS)[END_REF] and it required sophisticated compressed suffix array construction algorithms.

The time and main memory space required by compression algorithms is important. Building the compressed file within less main memory allows us compressing larger files without splitting them into chunks, yielding better compression in general. The fastest deterministic LZ78 compression algorithms require O(n) time, but O(n lg n) bits of main memory [START_REF] Fischer | Lempel Ziv computation in small space (LZ-CISS)[END_REF]. If the main memory is limited to O(n lg σ) bits (i.e., proportional to the input text size), then the time increases to O(n lg lg σ) [START_REF] Köppl | Lempel-Ziv computation in compressed space (LZ-CICS)[END_REF]. Finally, if we limit the main memory to O(z lg n) bits (i.e., proportional to the compressed text size, like the classic scheme), then the compression time becomes O(n(1 + lg σ/ lg lg n)) [START_REF] Arroyuelo | Succinct dynamic cardinal trees[END_REF], which improves the classic O(n lg σ) time. If we allow randomization, then the classic scheme yields O(n) expected time and O(z lg n) bits of space.

In this paper we show that the LZ78 compression can be carried out within just O(z lg σ) bits of main memory, which is less than any other previous scheme, and asymptotically less than the size of the compressed file, z(lg z + lg σ) bits. Ours are randomized and streaming algorithms. They read the text once from disk, and output the compressed file to disk as well, and therefore they may run within memory sizes unable to fit even the compressed file. One of our algorithms requires O(n) expected compression time, but may rewrite the output multiple times, whereas the other takes O(n lg σ) expected time but writes the output only once. Both are able to decompress the file in a single O(n)-time pass on disk and using O(z lg σ) bits of main memory, where previous decompression algorithms need to store the whole compressed text in main memory.

Our results hold under some simplifying assumptions on randomness. Nevertheless, our experimental results demonstrate that these assumptions do not affect the practical competitiveness of the new algorithms, which outperform current alternatives in space and/or time by a factor from 2 to 9.

To obtain the result, we build on a hash-based trie representation [START_REF] Poyias | m-Bonsai: a practical compact dynamic trie[END_REF], which has the advantage that the addresses of the nodes do not change as we insert new leaves, and that O(lg σ) bits are sufficient to encode the trie nodes since some of the information is implicit in their hash addresses. The main challenge is to design schemes so that the hash tables can grow as the LZ78 parsing progresses, so as to ensure that they have only O(z) cells without knowing z in advance.

LZ78 Compression

The LZ78 compression algorithm [START_REF] Ziv | Compression of individual sequences via variable length coding[END_REF] parses the text into a sequence of phrases. Assume we are compressing a text T [1.

.n] and we have already processed

T [1..i- 1] into r phrases B 0 B 1 B 2 • • • B r-1
, where phrase B 0 represents the empty string. Then, to compute B r we find the longest prefix T [i..j -1] (with j -1 < n) that is equal to some B q , with q < r. Then we define B r = B q . T [j], which is represented as the pair (q, T [j]), and we continue the parsing from T [j + 1].

If we add a unique terminator character to T , then every phrase represents a different text substring. We call z the final number of phrases generated. It is known that

√ n ≤ z = O(n/ lg σ n),
where σ is the size of the alphabet of T . The usual way to carry out the parsing efficiently is to use the so-called LZTrie. This is a trie with one node per phrase, where the root node corresponds to B 0 , and the node of B r = B q . T [j] is the child of the node of phrase B q with the edge labeled by T [j]. Since the set of phrases is prefix-closed, LZTrie has z nodes. Then, to process T [i..j-1], we traverse LZTrie from the root downwards, following the characters T [i], T [i + 1] . . . until falling out of the tree at a node representing phrase B q . Then we create a new node for B r , which is the child of B q labelled by T [j]. Since the trie has z nodes, it requires O(z(lg n + lg σ)) = O(n lg σ) bits for the parsing, which can be done in O(n lg σ) deterministic time (using binary search on the children) or O(n) randomized time (using hash tables to store the children, whose sizes double when needed).

The usual way to represent the LZ78 parsing in the compressed file consists of two (separate or interlaced) arrays, S[1..z] of z lg σ bits, and A[1..z] of z lg z bits. If B r = B q . T [j] is a phrase, then we represent it by storing A[r] = q and S[r] = T [j]. For decompressing a given phrase B r , we follow the referencing chain using array A, obtaining the corresponding symbols from array S, until we read a 0 in A. An alternative way to represent the LZ78 parsing [START_REF] Arroyuelo | Stronger Lempel-Ziv based compressed text indexing[END_REF] uses a succinct encoding of LZTrie, which uses just 2z + z lg σ + o(z) bits, 2z + o(z) for the topology and z lg σ for the labels. It also stores an array L[1..z], such that L[r] stores the preorder number of the LZTrie node corresponding to phrase B r . This array requires z lg z bits. To extract the text for phrase B r , we start from the node with preorder L[r] in LZTrie, and obtain the symbols labeling the upward path up to the root, by going successively to the parent in the trie. Using succinct tree representations that support going to the parent in constant time, this procedure also yields O(n) total decompression time.

This second representation is more complex and uses slightly more space than the former, more precisely, the 2z + o(z) bits for the tree topology. Yet, it is sometimes preferred because it allows for operations other than just decompressing T . For instance, Sadakane and Grossi [START_REF] Sadakane | Squeezing succinct data structures into entropy bounds[END_REF] show how to obtain any substring of length of T in optimal O( / lg σ n) time (i.e., in time proportional to the number of machine words needed to store symbols). In this work, a different representation of LZTrie will allow us carrying out the compression within O(z lg σ) bits of main memory.

Previous Work on LZ78 Construction

A classic pointer-based implementation of LZTrie, with balanced binary trees to handle the children of each node, carries out the compression in O(n lg σ) time and O(z lg n) bits of space.

Jansson et al. [START_REF] Jansson | Linked dynamic tries with applications to LZ-compression in sublinear time and space[END_REF] introduce a particular trie structure to represent LZTrie, which still uses O(z lg n) bits of space but reduces the construction time to

O n lg σ • (lg lg n) 2
lg n lg lg lg n . The algorithm needs two passes on the text, each of which involves n lg σ bits of I/O if it is stored on disk.

Arroyuelo and Navarro [START_REF] Arroyuelo | Space-efficient construction of Lempel-Ziv compressed text indexes[END_REF] manage to perform a single pass over the text, in exchange for 2z lg z additional bits of I/O, and a total time of O(n(lg σ +lg lg n)). The peak memory usage is z(lg n + lg σ + 2) bits. They use the compact LZTrie representation described in the previous section. An obstacle to further reducing the space is that they need to build the whole LZTrie before they can build Reference RAM space in bits Compression time Classic [START_REF] Ziv | Compression of individual sequences via variable length coding[END_REF] O

(z lg n) O(n lg σ) O(z lg n) O(n) * Fischer et al. [8] (1 + )n lg n + O(n) O(n/
2 ) Köppl and Sadakane [START_REF] Köppl | Lempel-Ziv computation in compressed space (LZ-CICS)[END_REF] O(n lg σ) O(n lg lg σ)

Jansson et al. [10] O(z lg n) O n lg σ • (lg lg n) 2 lg n lg lg lg n Arroyuelo et al. [1] z(lg n + lg σ + 2) O n lg σ • 1 lg lg n
Arroyuelo and Navarro [START_REF] Arroyuelo | Space-efficient construction of Lempel-Ziv compressed text indexes[END_REF] z(lg n

+ lg σ + 2) O(n lg σ + n lg lg n) This paper O(z lg σ) O(n) *
Table 1: Previous and new LZ78 compression algorithms. Times with a star mean expected time of randomized algorithms. We first list the classic schemes, then the deterministic methods, from fastest and most space-consuming to slowest and least space-consuming. At the end, our randomized method uses less space than all the others, and also matches the fastest ones in expectation.

the array L, because preorder numbers vary as new leaves are inserted. Later improvements on dynamic tries introduced by Arroyuelo et al. [START_REF] Arroyuelo | Succinct dynamic cardinal trees[END_REF] reduce the time to O n lg σ lg lg n . Notice that this is O(n) for small alphabets, σ = polylog(n). However, the peak space usage remains the same.

Fischer et al. [START_REF] Fischer | Lempel Ziv computation in small space (LZ-CISS)[END_REF] finally obtained linear worst-case time. They construct the LZ78 parsing using (1

+ )n lg n + O(n) bits of space in O(n/ 2 ) time.
Recently, Köppl and Sadakane [START_REF] Köppl | Lempel-Ziv computation in compressed space (LZ-CICS)[END_REF] showed how to construct the parsing in O(n lg lg σ) time, using O(n lg σ) bits of working space; note this is Ω(z lg n).

Table 1 shows all these previous results, and our contribution in context. Our results hold under some simplifying assumptions that are described in Section 8.

Dynamic Compact Tries

We will make use of the following data structure to maintain a dynamic trie of up to t nodes that uses O(t lg σ) bits, while supporting insertion of edges, and navigation upwards and downwards from nodes, within constant randomized time [START_REF] Poyias | m-Bonsai: a practical compact dynamic trie[END_REF]. The structure has two components:

1. A closed hash table H[0..M -1]
, where M = m/α, m is an upper bound to the number of nodes, and the constant α < 1 is the load factor to use. Table H is a simple array that stores information on the nodes of the trie, using only lg σ + O(1) bits per entry. 2. An array D[0..M -1] to store information about the collisions (all entries initialized with value -1).

Each trie node y is identified with the position where it is stored in H; sometimes we will write p(y) explicitly to refer to this position. This position will not change with time. The root is placed at an arbitrary position, say H[0]. Every other node y is represented by a pair (x, c), where x is (the position in H of) the parent of y and c is the character labeling the edge between x and y.

The hash function used to place y in H is h(y) = ((a • w(y)) mod P ) mod M, where a is an integer chosen at random in [1, P -1], P is the first prime such that P > M • σ, and w(y) = p(x) • σ + (c -1). The value we store in the cell of H associated with y is v(y) = ((a • w(y)) mod P ) div M.

With this mechanism, since P = O(M σ) [9, p. 343], it holds v(y) = O(σ), and thus the values stored in H require lg σ +O(1) bits. With this information we can still reconstruct (a•w(y)) mod P = v(y)•M +h(y), and then w(y) = a -1 •(a•w(y)) mod P , where a -1 mod P is easily computed from a and stored with the index. From w(y) we recover the pair (x, c), which allows us traversing the trie upwards.

On the other hand, to insert a new child y = (x, c) from the position p(x), we compute h(y) and try to write v(y) at H[h(y)]. If the cell is free (which we signal with D[h(y)] = -1), then we write H[h(y)] ← v(y) and D[h(y)] ← 0. If the cell is not free, we probe consecutive positions H[p] with p = (h(y) + k) mod M , for k = 1, 2, . . .. The following cases may occur:

1. D[p] = -1, in which case we terminate with H[p] ← v(y) and D[p] ← k, so that D[p]
indicates the number of probes between h(y) and the final position p where y is finally written. Note that p will become p(y), and from p(y) we can recover h(y) without knowing y, with h(y)

= (p(y) -D[p(y)]) mod M . 2. D[p] = -1, H[p] = v(y), and (p -D[p]) mod M = h(y), thus node y is already stored in H, so we should not insert it. 3. D[p] = -1, but H[p] = v(y) or (p -D[p]) mod M = h(y), thus the cell is
occupied by another node and we must continue with the next value of k.

Case 2 also shows how to traverse the trie downwards, from the current node towards its child labeled by c, to find the node y = (x, c).

Note that the values stored in D are constant in expectation, as they record the insertion time for each element. Poyias et al. [START_REF] Poyias | m-Bonsai: a practical compact dynamic trie[END_REF] show how D can be represented with a data structure using O(z) bits and constant amortized-time operations. We refer the reader to their article for further details.

Using a Fixed Hash Table

In this section we show how to do the parsing of T [1..n] within O(n lg σ/ lg σ n) bits of main memory. This space is already O(z lg σ) on incompressible texts; we will later achieve it for all texts.

We use a compact dynamic trie to build the LZTrie associated with the LZ78 parse of T , and to compress T accordingly. We set m to an upper bound on the number of LZTrie nodes: m is the smallest number with m(lg σ m -3) ≥ n. Thus m = Θ(n/ lg σ n). Further, we will use an array L[0..z] to store in L[r] the position in H where the LZTrie node of block B r is stored. Each entry of L takes lg M = lg n + O(1) bits, but the array is generated directly on disk.

To perform the parsing of a new phrase T [i..j], we start from the trie root (say, x 0 , with p(x 0 ) = 0), and use the mechanism described in the previous section to compute x 1 = (x 0 , T [i]), x 2 = (x 1 , T [i+1]), and so on until x j-i+1 = (x j-i , T [j]) does not exist in the trie. At this point we insert x j-i+1 = (x j-i , T [j]), write to disk the next value L[r] ← p(x j-i+1 ), and continue with T [j + 1..n].

Overall, compression is carried out within the O(n lg σ/ lg σ n) bits of main memory used by H and D, in O(n) expected time if H is chosen from a universal family of hash functions, and T and L are read/written from/to disk in streaming mode. When we finish the parsing, we write H and D at the end of L in the file, and add some header information including n, σ, M , P , a, a -1 .

Decompression can also be made in streaming mode and using memory space only for H and D, which is not possible in classical schemes where each phrase is stored as a pointer to its earlier position in the file. We load the LZTrie into memory (i.e., tables H and D). Now we read the consecutive entries of L[1..z] in streaming mode. For each new entry L[r] = p, we start from H[p] and decode x 0 = (x -1 , c -1 ) from it; then we decode x -1 = (x -2 , c -2 ), and so on, until we reach the root x -s = L[0]. Then we append c -s c -s+1 . . . c -2 c -1 to the decompressed text in streaming mode. The stack may require up to z lg σ bits in extreme cases, but this is still within our main memory budget. Its use can also be avoided in standard ways, at the expense of increased I/Os.

Note that this structure permits retrieving the contents of any individual block B r , by traversing the LZTrie upwards from L[r], just as done for decompression. This can make it useful as a succinct data structure as well.

The obvious disadvantage of this simple scheme is that it uses more than O(z lg σ) bits of space when T is highly compressible, z = o(n/ lg σ n) (that is, when it is most interesting to compress T !). A simple workaround is to start assuming that z = O( √ n), since √ n is the smallest possible value for z. If, during the parsing, this limit is exceeded, we double the value of z and repeat the whole process. Since we may rerun the process O(lg z) times, the total expected time is O(n lg z) = O(n lg n) (in LZ78, lg z = Θ(lg n)). In exchange, the main memory space is now always O(z lg σ) bits. Further, the extra space added to the compressed file due to the tables H and D is just O(z lg σ). Apart from the increased time, a problem with this scheme is that it reads T several times from disk, and thus it is not a streaming algorithm. In the next sections we explore two faster solutions that in addition scan T only once.

Using a Growing Table

We can obtain O(z lg σ) bits of space for any text by letting H and D grow as more blocks are produced along the parsing. We start with a hash table of size √ n/α 2 , since √ n is a lower bound on z. Then, whenever the load factor in H reaches α, we allocate a new table H (and D ) with size multiplied by 1/α, and load them with all the current trie nodes. We will read T only once, but we will still perform multiple rewriting passes on L.

The main challenge is how to remap all the nodes x from H to H , since their position p(x) in H are their identity, which is mentioned not only in L but also in their children y = (p(x), c). That is, in order to map y to its new position p (y) in H , we need to know the mapped position p (x) of its parent x, that is, we must map the LZTrie nodes top-down. Yet, we cannot simply perform a DFS traversal on LZTrie, because we cannot efficiently enumerate the children of a node x in less than O(σ) time.

We remap the nodes as follows. We traverse L from left to right (on disk), and traverse upwards from each position L[r] in H up to the root. All the nodes from the parent of L[r] must already exist in H , so we stack the symbols traversed in the upward path on H and use them to traverse downwards in H from the root. Then we insert in H (and D ) the new node that corresponds to L[r], and rewrite L[r] with the new position in H . If B r corresponds to T [i..j], then our retraversal costs O(j-i) time, so the expected time to retraverse T [1..n ] is O(n ). Since we perform O(lg z) passes, the total cost may reach O(n lg z) = O(n lg n).

We can reduce the time to O(z lg σ n) = O(n) by storing, when we have to load H , O(z/ lg σ n) sampled nodes of H in a (classic) hash table W , which stores the position in H of each sampled position in H. Table W uses O(z lg σ) bits, which is within our budget. We will guarantee that every node of LZTrie whose depth is a multiple of lg σ n and whose height is at least lg σ n will be sampled. This ensures that O(z/ lg σ n) nodes are sampled and that we traverse less than 2 lg σ n nodes of H from any cell L[r] before reaching a sampled node, from which we can descend in H and insert L[r] in time O(lg σ n). Thus we do the translation in O(|L| lg σ n) time. Since the size of L grows by a factor of 1/α each time we create a larger table, the total work amounts to O(z lg σ n).

To obtain the sampling invariant, we start by sampling the root. Then, every time we traverse from the node of L[r] upwards, if we traverse lg σ n cells or more before finding a sampled node, we sample the node we traversed that is at distance lg σ n from the sampled node we reached.

Once H and D are built, we continue with them and discard H and D. The peak space usage of the tables, when old and new ones are active, is (1/α 2 + 1/α)z lg σ + O(z) = O(z lg σ) bits. Note that we can always keep the entries of L within lg z + O(1) bits, slightly expanding them when we retraverse L to rewrite the new positions in H . At the end, L may need to point to a table H whose size is z/α 2 , thus using z lg z + O(z) bits. To store H and D, we first write a bitvector B of length at most z/α 2 indicating which entries are = -1 in D. This requires O(z) bits. Only the z filled entries of H and D are then written to the compressed file. The final compressed file size is then z(lg z + lg σ) + O(z) bits.

Using Multiple Hash Tables

A way to avoid rebuilding the hash table is to create additional hash tables apart from the original one, H 0 = H. When the load factor of H reaches α, we allocate a new table H 1 , with |H 1 | = 2|H 0 |, where all the subsequent insertions will take place. When H 1 becomes full enough, we create H 2 , with |H 2 | = 2|H 1 |, and so on, each time doubling the previously allocated space. Each table H h has its own value M h , prime P h , and so on.

To properly address the nodes, we need to build a global address that can point to entries in any table. We regard the tables as their concatenation, that is,

H 0 H 1 H 2 .

. . The addresses within table H h are built by adding |H

0 H 1 . . . H h-1 |
to the normal address computation within H h . The prime P h must then be larger than (M 0 + M 1 + . . . + M h ) • σ, so as to store any element (p(x), c) where p(x) is a global address. This requires only O(1) extra bits per cell to store P h /M h ≤ 2σ.

Assume we are at a node x in a table H g and want to add a child y = (x, c) in the current table H h . The entry (p(x), a) will be inserted in H h , leaving no indication in H g of the existence of y. This means that, if we want to descend from x by c, we must probe tables H g , H g+1 , . . . , H h to see if it was inserted in later tables. Therefore, the cost of traversing towards a child grows to O(lg z), as we can build that many tables during the parsing. However, since the children are inserted later than their parents, the current table index does not decrease as we move down from the root towards the node where we will insert the new block, and thus we do these O(lg z) probes once per inserted block, for a total time of O(z lg z) = O(n lg σ).

Instead, the parent x is decoded immediately from y = (p(x), a), since p(x) is a global address, and this allows decompressing in O(n) time. Finding the table H g from p(x) is a matter of dividing p(x) by √ n and then finding the logarithm in base 2, which is done in constant time in most architectures (and in theory, using constant precomputed tables of small size).

This technique has the advantage that it treats T and L in streaming mode, as it does not have to retraverse them. The values written on L are final (note that their width grows along the process, each time we start using a new table). These can be compacted as in the previous section if we are willing to perform a second pass on L.

Simplifying Assumptions

Our expected-case analysis inherits some simplifications from Poyias et al. [START_REF] Poyias | m-Bonsai: a practical compact dynamic trie[END_REF], when it assumes constant expected time for hashing with linear probing.

A first one is that analyses usually assume that the hash function is chosen independently of the set of values to hash. In our scheme, however, the values (p(x), c) to hash depend on the hash function h(x) itself. So, at least in principle, the typical assumptions to prove 2-independence do not hold, even if we changed our function to the standard ((a 0 + a 1 • w(y)) mod M ) mod P for randomly chosen a 0 and a 1 .

File Name

Size Another issue is that 2-independence may not be sufficient to assume randomness in the case of linear probing. This has only been proved assuming 5-independence [START_REF] Pagh | Linear probing with 5-wise independence[END_REF][START_REF] Patrascu | On the k -independence required by linear probing and minwise independence[END_REF]. To make it 5-independent, the component a • w(y) of our hash function should become a 0 + a 1 w(y) + a 2 w(y) 2 + a 3 w(y) 3 + a 4 w(y) 4 . We do not know how to invert such a function in order to find w(y) given h(y) and v(y).

In the next section we show, however, that those theoretical reservations do not have a significant impact on the practical performance of the scheme.

Experimental Results

In this section we experimentally evaluate our new algorithms with some previous implemented alternatives. We measure compression and decompression time, RAM usage and overhead of the final file size compared with the standard LZ78 format. All the experiments were performed on an Intel(R) Core(TM) i7-5500U CPU at 2.40 GHz. The operating system was Ubuntu 16.04.2 LTS, version 4.4.0-72-generic Linux kernel. Our compressors were implemented in C++11, using g++ version 4.8.4.

The texts considered are a highly compressible XML text, an English text, and a less compressible Protein file, all obtained from the Pizza&Chili Corpus5 . We also used a DNA file generated by extracting a prefix of a human genome 6 . Table 2 lists the test files used and their main statistics. For the compression ratio we assume that each of the z phrases gives the parent phrase number and the symbol. For the former, the next 2 i phrases use i + 1 bits, starting from the second with i = 0. For the latter, we use lg σ bits.

Figure 1 shows the maximum RAM used by each structure during compression, and the resulting compression time. Our approaches are labeled HLZ (fixed hash table of maximum size, no rebuilding), MHLZ (multiple hash tables) and GHLZ (growing hash tables, no sampling). We obtain tradeoffs by using various load factors for the hash tables, 1/α = 1.05, 1.10, 1.20, 1.40, 1.60.

As previous work, we include LZ78-Min, the compact representation of Arroyuelo and Navarro [START_REF] Arroyuelo | Space-efficient construction of Lempel-Ziv compressed text indexes[END_REF], and LZ78-UC, their uncompressed baseline, both implemented in C. It can be seen that MHLZ always outperforms GHLZ in space/time, using 1.0-2.2 bits and 0.2-0.3 µsec per symbol with 1/α = 1.40. For the same space, the overhead of using multiple tables is lower than that of rebuilding the table, which implies rereading the L array from disk. In general, the time of MHLZ is very sensitive to high load factors, without significantly improving the space. With a sufficiently low load factor, instead, it outperforms all the others in time and space. It even gets close to the time of HLZ, always below 0.2 µsec, with much less space (with the exception of Proteins, where the final-size guess of HLZ is nearly optimal). The maximum space usage of GHLZ occurs when it has to expand the table, at which moment it has the old and new tables in RAM. This requires more space than MHLZ even when the MHLZ tables are emptier on average. LZ78-Min, instead, requires 2-3 times more space and is up to 4 times slower. Finally, LZ78-UC requires 6-9 times more space than MHLZ, and is not faster than HLZ.

Figure 2 shows the RAM used by each structure during decompression. This time GHLZ always obtains the best time of MHLZ but using slightly less space. GHLZ uses 0.9-1.8 bits and 0.1-0.2 µsec per symbol, even outperforming HLZ, which uses much more space (except on Proteins). GHLZ does not need to make the hash tables grow at decompression, thus it is much faster and uses less space than MHLZ, which has emptier tables. MHLZ is faster than for compression because it traverses the paths upwards, but it still uses multiple tables, and this poses some time overhead. LZ78-Min and LZ78-UC are identical for decompression, requiring 2-3 times more space but being 2-3 times faster than GHLZ.

Finally, Figure 3 shows the ratio between the actual compressed file size and the output of a classical LZ78 compressor (see Table 2). We exclude the HLZ baseline because it does not really compress. While MHLZ poses 30%-40% of overhead, GHLZ requires 25%-35%. We note that, to reach this overhead, we need to use 1/α = 1.1 or less, that is, almost the slowest. In this case, it is preferable to use GHLZ, which uses 1-3 bits and 0.5-0.8 µsec per symbol for compression and 0.1-0.2 µsec for decompression. If we want to have the fastest MHLZ compression times, we must accept an overhead of 40%-45%. On the other hand, LZ78-Min has an overhead of 4%-15%.

Conclusions

We have presented new LZ78 compression/decompression algorithms based on hashing, which under some simplifying assumptions use O(z lg σ) bits of main memory in expectation, while running in O(n lg σ) time for compression and O(n) time for decompression, where n is the text length, z the number of LZ78 phrases, and σ the alphabet size. Our algorithms read the text once, in streaming mode, and write the output to disk. There exists no previous algorithm using so little main memory.

Our experiments show that our new methods use 2-3 times less space for compression than the most space-efficient implemented compressor in the literature, while being up to 4 times faster. Compared to a classical baseline, our compressor uses 6-9 times less space and is only 50% slower. Our decompressor uses 2-3 times less space than both baselines, but it is 2-3 times slower.

For example, our compressor can use up to 3 bits and 0.8 µsec per symbol and our decompressor up to 2 bits and 0.2 µsec per symbol, posing a space overhead around 30% over the optimally compressed file.

Our compressors and the competing algorithms are publicly available at https://github.com/rcanovas/Low-LZ78.

An interesting line of future work is to use these hash-based tries as compressed text representations that retrieve any text substring [START_REF] Sadakane | Squeezing succinct data structures into entropy bounds[END_REF], or for the compressed-space construction of LZ78-based text indexes [START_REF] Arroyuelo | Space-efficient construction of Lempel-Ziv compressed text indexes[END_REF].

  Thus S[r], S[A[r]], S[A[A[r]], . . . obtains B r in reverse order in O(|B r |) time, and the complete text is decompressed in O(n) time.

  Note that the O(z) bits spent in L can be eliminated with a final pass on L replacing L[r] by rank 1 (B, L[r]), which is the number of 1s in B up to position L[r]. This can be computed in O(z) time, and the values can be recovered in O(z) time at decompression time using the complementary query select 1 (B, L[r])[START_REF] Clark | Compact PAT Trees[END_REF].

Fig. 1 :

 1 Fig. 1: Maximum RAM and time used during compression.

Fig. 2 :

 2 Fig. 2: Maximum RAM and time used during decompression.

Fig. 3 :

 3 Fig. 3: Maximum RAM used at compression versus ratio of the final file size over the classical output size.

Table 2 :

 2 Text files used in the experiments.

http://pizzachili.dcc.uchile.cl/texts

http://hgdownload.cse.ucsc.edu/goldenPath/hg18/bigZips/est.fa.gz

Acknowledgements

We thank the reviewers for their insightful comments.

This collaboration started during the Dagstuhl Seminar 16431


A Twenty-Year Citation Analysis of the Knowledge Outflow and Inflow Patterns from the Journal of Product Innovation Management

 Shikhar Sarin, Christophe Haon, and Mustapha BelkhoujaSince its inception in 1984, an emphasis on cross-functionality and interdisciplinary research was encrypted into the DNA of the Journal of Product and Innovation Management (JPIM). This essay explores the extent to which the journal has served as a platform for exchange of ideas between different disciplines by examining knowledge outflow and inflow with other scientific journals and disciplines over a 20-year period (1994-2013). Based on an extensive bibliometric database, we gain insights about how JPIM has evolved. We show that the journal has become a gatekeeper, importing knowledge mostly from the marketing and management literatures, and exporting knowledge to the technology and innovations management and the operations management domains.

S

ince its launch in 1984 the Journal of Product Innovation Management (JPIM) has come to be regarded as one of the premier journals in the management of technology and innovation (Linton and Thongpapnl, 2004;[START_REF] Sarin | A bibliometric analysis of the knowledge exchange patterns between major technology and innovation management journals (1999-2013[END_REF][START_REF] Shafiq | Thinking inside the box? Intellectual structure of the knowledge base of innovation research (1988-2008)[END_REF]. JPIM's growing stature is further underscored by the journal recording an Impact Factor of 4.305 in 2017-the highest in its history (https://onlinelibrary.wiley.com/journal/15405885).

JPIM's aims and scope describes its mandate as:

The Journal of Product Innovation Management is an interdisciplinary, international journal that seeks to advance our theoretical and managerial knowledge of product and service development. The journal publishes original articles on organizations of all sizes (start-ups, small-medium enterprises, large) and from the consumer, business-to-business, and institutional domains. The journal is receptive to all types of quantitative and qualitative methodologies. Authors across the world from diverse disciplines and functional perspectives are welcome to submit to the journal. (https:// onlinelibrary.wiley.com/page/journal/15405885/ homepage/productinformation.html)

An emphasis on cross-functionality and interdisciplinary research was encrypted into the journal's DNA since its inception. In this essay, we explore to what extent JPIM has stayed true to its original mandate and served as a platform for exchange of ideas between different disciplines.

Specifically, we examine how JPIM has influenced other scientific journals and disciplines, and in turn, how much of an impact other scientific journals and disciplines have had on the research published in JPIM over a 20-year period (1994-2013). [START_REF] Biemans | Twenty years of the Journal of Product Innovation Management: History, participants, and knowledge stock and flows[END_REF] explored some of these knowledge exchange patterns over the first 20 years of JPIM's existence. This essay offers an updated and in-depth analysis of the knowledge outflow and inflow patterns of JPIM. Other journals such as Industrial Marketing Management [START_REF] Di Benedetto | Patterns of knowledge outflow from Industrial Marketing Management to major marketing and specialized journals (1999-2013): A citation analysis[END_REF], Journal of the Academy of Marketing Science [START_REF] Malhotra | The impact of the Academy of Marketing Science on marketing scholarship: An analysis of the research published in JAMS[END_REF], and Journal of International Business Studies [START_REF] Inkpen | An analysis of twenty-five years of research in the Journal of International Business Studies[END_REF] have also engaged in similar introspections over the years.

Methodology

We employed bibliometric analysis to investigate the impact JPIM has had on other academic journals by analyzing how often JPIM is cited by these journals (i.e., knowledge outflow). Similarly, we examine the influence of other academic journals on JPIM (i.e., knowledge inflow) by looking at how often articles published in JPIM cited these journals [START_REF] Biemans | Twenty years of the Journal of Product Innovation Management: History, participants, and knowledge stock and flows[END_REF][START_REF] Di Benedetto | Patterns of knowledge outflow from Industrial Marketing Management to major marketing and specialized journals (1999-2013): A citation analysis[END_REF][START_REF] Sarin | A bibliometric analysis of the knowledge exchange patterns between major technology and innovation management journals (1999-2013[END_REF]. For the purpose of this essay, we extracted citation data from every article published in 336 journals in major business disciplines from the Web of Science (WoS). Our bibliometric database contained data on 5,998,130 citations drawn from 135,559 articles published in these journals from 1994 to 2013.

Such citation-based analyses are widely accepted as standard methodology in assessing not only the influence of journals, but also knowledge flow patterns within and among disciplinary domains (e.g., [START_REF] Clark | The intellectual ecology of mainstream marketing research: An inquiry into the place of marketing in the family of business disciplines[END_REF][START_REF] Nelson | Knowledge flows between advertising and other disciplines: A social exchange perspective[END_REF][START_REF] Shafiq | Thinking inside the box? Intellectual structure of the knowledge base of innovation research (1988-2008)[END_REF]. However, such bibliometric analyses are limited in that they are unable to distinguish the level of intellectual indebtedness. They cannot distinguish between citations that truly reflects a transfer of knowledge versus ones that are largely perfunctory [START_REF] Biemans | Twenty years of the Journal of Product Innovation Management: History, participants, and knowledge stock and flows[END_REF]. [START_REF] Sarin | A bibliometric analysis of the knowledge exchange patterns between major technology and innovation management journals (1999-2013[END_REF] further note that journals differ in the number of articles published per year, and the number of references cited per article. Hence in addition to the raw numbers of citations, we adopted the approach recommended by Di Benedetto et al. ( 2018) and report the citation data in normalized percentage of all references cited in that journal in that year, as recorded in our database. The journal impact factors (IF) were extracted from the Journal Citation Reports (JCR) database from Clarivate Analytics (formerly known as ISI-Institute for Scientific Information).

Findings

Knowledge Outflow Patterns-Impact of JPIM on Other Journals and Disciplines

JPIM's influence on other journals was measured in terms of the number of times these journals cited JPIM (e.g., [START_REF] Biemans | Twenty years of the Journal of Product Innovation Management: History, participants, and knowledge stock and flows[END_REF][START_REF] Sarin | A bibliometric analysis of the knowledge exchange patterns between major technology and innovation management journals (1999-2013[END_REF]. distinction between management, organization science, and entrepreneurship journals, these journals were grouped together in subsequent analyses due to the overlap between their domains.

From Tables 1 and2 it can be seen that 7 of the Top 10 journals citing JPIM over this period were TIM journals, while the remaining three were marketing. These Top 10 journals accounted for nearly 60% of 1, with each accounting for less than 1% of the citations received by JPIM over the 20-year period. It is worth noting that the journals from the information systems domain are conspicuously absent from the list of top 50 journals citing JPIM.

Next, we examine the evolution in the citation pattern of JPIM over the years. Figure 1 presents the trend in the number of citations of JPIM across the different disciplinary clusters. The numbers of citations of JPIM in the TIM and MKT journals show a steady and large increase from 1994 to 2013, with a significant jump in the number of citations from the TIM journals starting in 2010. The increase in the number of citations is particularly noticeable after 2005, and coincides with a gradual increase in the number of articles published in JPIM in the previous years [START_REF] Biemans | Twenty years of the Journal of Product Innovation Management: History, participants, and knowledge stock and flows[END_REF].

It should be noted that the TIM citation numbers presented in figures are without self-citations. If self-citations were to be included, the trend of JPIM citations in TIM journals would be even more pronounced. The numbers of citations of JPIM in the OM and MGT/ENT/ORG journals also show a steady, albeit much slower increase over this period. However, the numbers of JPIM citations in OM and MGT/ ENT/ORG journals trail the TIM and MKT citations by a wide margin. Overall, the raw numbers of JPIM citations in the OM and MGT/ENT/ORG journals remain low over the period of interest. Not surprisingly, given the growth in the number of citations across the different disciplinary clusters, the JCR Impact Factor for JPIM shows an increasing trend from 1994 to 2013.

Figure 2 presents the trends in the citations of JPIM in different disciplinary clusters in normalized percentage terms. This is done to account for differences between the journals in the number of articles published per year, and the number of references cited per article [START_REF] Di Benedetto | Patterns of knowledge outflow from Industrial Marketing Management to major marketing and specialized journals (1999-2013): A citation analysis[END_REF][START_REF] Sarin | A bibliometric analysis of the knowledge exchange patterns between major technology and innovation management journals (1999-2013[END_REF].

Figure 2 shows that after accounting for between 40% and 60% of all the citations of JPIM in the mid-late 90s, TIM journals seemed to have settled around 50% of all JPIM citations starting 2004.

MKT is the second most important citing cluster in Figure 2, holding relatively steady at accounting for about 35% of all citations of JPIM since 2000, after having recorded as high as 45% in the late 90s. There is a slow but steady increase in the percentage of JPIM citations in OM journals, which accounted for about 10% of all JPIM citations by the end of 2013. The percentage of JPIM citations in the MGT/ORG/ENT cluster showed a gradual increase in the mid-late 90s, then decreased steadily from 2001 to 2006 (from 28% to 5%), and has held relatively steady around 10% since 2008.

Knowledge Inflow Patterns-Impact of Other Journals and Disciplines on JPIM

In this section, we focus on how research published in JPIM was influenced by other journals. Not counting self-citation, the other 49 journals identified in Table 1 were cited in JPIM 12,949 times from 1994 to 2013. During this period, the five journals most frequently cited by research published in JPIM were Journal of Marketing (15.5% of all citations), Journal of Marketing Research (11.7%), Strategic Management Journal (11.3%), Management Science (8.4%), and Academy of Management Journal (5.8%). Organization Science and Research Policy were also cited quite frequently, accounting for 5.2% and 4.7% of the outgoing citations, respectively.

Examining the knowledge inflow by disciplinary clusters reveals that over the 1994-2013 period, studies published in JPIM drew upon MKT journals most heavily (43.6% of all outgoing citations from Table 1), followed by journals in the management/entrepreneurship/organizational (MGT/ENT/ORG) domains (37.7%). Articles published in JPIM drew upon TIM (16.1%) and Operations Management (2.7%) domains to a much lesser extent. Trends in these outgoing citation patterns over the years provide some additional insights.

Figure 3 presents the trends in citation of the disciplinary clusters in JPIM (in numbers) from 1994 to 2013. We see an explosion in number of citations in JPIM from 2008 onwards. The vast majority of new citations seem to be coming from articles published in MKT and MGT/ENT/ORG, and to a much lesser extent in the TIM journals. In the last few years of the period under consideration, the rate of increase in outgoing citations for MGT/ENT/ORG seems to be outpacing those from the MKT literature. This suggests an increasing reliance on the body of knowledge from the broader management literature.

The significant jump in citations from MKT and MGT/ENT/ORG starting in 2010 corresponds to a temporary increase in the number of articles published in JPIM from 2010 to 2013. The temporary increase in the number of articles published was necessitated by a need to clear a significant backlog of accepted articles and special issues that had been previously approved. 1 Figure 4 shows the trend in outgoing citations for other disciplines as a percentage of the journals cited in JPIM. It can be seen that in percentage terms citations from MKT have remained relatively stable between 40% and 50%. However, citations from the MGT/ENT/ ORG journals have gradually increased from 20% to 1 The authors thank Gloria Barczak for this insight. around 45% of the journals cited in JPIM from 1994 to 2013. This coincides with a gradual decline in citation of TIM journals from 33% in 1994 to 13% in 2013. While the citation of OM journals increased slightly over the years, its overall level remains low at around 4%.

Net Knowledge Flow Patterns-Difference in Citation Flows to and from JPIM

Next, we use the data presented in Table 1 to examine the difference between the citations of JPIM by each journal, and the citation of each journal in JPIM from 1994 to 2013. JPIM is regarded as a net importer of knowledge if JPIM cites the journal more frequently (outgoing citations) than it is cited by the journal (incoming citations). On the other hand, JPIM is a net exporter of knowledge to a journal if JPIM is cited by the other journal (incoming citations) more frequently than the other journal is cited in JPIM (outgoing citations).

Over the 20-year period under examination, journals where JPIM is a net exporter of knowledge show a positive balance in the last column of Table 1, and journals where JPIM is a net importer of knowledge show a negative one. Journals to which JPIM has the highest export differential are Technovation, Industrial Marketing Management, and R&D Management. On the other hand, JPIM has the highest knowledge import differential with Journal of Marketing, Journal of Marketing Research, and Strategic Management Journal.

Table 3 presents a year-by-year analysis of the number of citations of JPIM minus the number of citations by JPIM for each disciplinary cluster. Again, a net export situation reflects in a positive balance, and a net import situation in a negative one. Increasingly, JPIM seems to be acting as a gatekeeper, importing heavily from MKT and MGT/ENT/ORG, and exporting more and more to other TIM journals (and OM journals to a lesser extent).

A graph of this data, presented in Figure 5, shows that JPIM's net knowledge deficit with MKT and MGT/ENT/ORG increased substantially starting 2008. The net knowledge deficit with MGT/ENT/ORG seems to be increasing at a more rapid rate than MKT.

Implications

This essay conducted a 20-year bibliometric analysis of the knowledge outflow and inflow patterns from JPIM using a database containing nearly 6 million citations drawn from over 135,000 articles published in 336 major business journals. Our findings suggest that JPIM has made significant strides toward fulfilling its mandate to serve as an interdisciplinary platform for exchange of ideas on new product development and innovation management. However, work remains to be done. A significant number of the JPIM's knowledge outflow (i.e., JPIM's impact) from 1994 to 2013 came from TIM and MKT journals, and to much lesser extent OM and MGT/ENT/ORG journals. This is not surprising given that a majority of the authors publishing in JPIM during this period came from a marketing background [START_REF] Biemans | Twenty years of the Journal of Product Innovation Management: History, participants, and knowledge stock and flows[END_REF]. While both OM and MGT/ENT/ORG journals have shown a very slow uptick in their citations of research published in JPIM, the percentage of JPIM citations coming from MGT/ENT/ORG journals has gone down slightly over time. Both OM and MGT/ENT/ORG journals only accounted for a relatively modest percentage of overall citations of JPIM from 1994 to 2013.

This is somewhat surprising, given the obvious synergy between the ENT and TIM domains. Additionally, a lot of research published in JPIM relates to organizational and team-related factors affecting innovation-subjects that should be of inherent interest to the strategy, organization science, and organizational behavior literatures [START_REF] Biemans | Twenty years of the Journal of Product Innovation Management: History, participants, and knowledge stock and flows[END_REF]. Another surprising finding of our analysis was the noticeable absence of Management Information Systems (MIS) journals from the list of the Top 50 journals citing JPIM most frequently over the 1994-2013 period. This suggests that while JPIM has done an outstanding job of disseminating its knowledge in the TIM and MKT disciplines, significant outreach work remains to be done in the OM, MGT/ENT/ORG, and MIS domains. JPIM needs to be more proactive in reaching out to scholars in these domains.

We would encourage the incoming JPIM editorial team to consider commissioning innovation-related special issues at the intersection of OM, MGT/ENT/ ORG, and MIS to encourage scholars in these areas to publish in JPIM. Efforts should also be made to recruit and invite leading scholars in these domains to publish influential thought pieces in JPIM. This in turn would increase the visibility of JPIM in these domains.

Knowledge inflow patterns (i.e., the impact of other journals/disciplines on JPIM) from 1994 to 2013 suggest a maturing of the knowledge base from which JPIM draws upon. Over the period under examination, research published in JPIM came to rely upon other TIM journals less and less. While the total number of TIM citations in JPIM have grown modestly, their share of the outgoing citations has gone down steadily over the years. Since 2008, JPIM seems to have moved significantly in drawing upon MKT and MGT/ENT/ORG domains, and presumably upon more basic and established theories. Reliance on MGT/ENT/ORG journals seems to be fast outpacing the reliance on the MKT journals in recent years. A more detailed breakdown of the MGT/ENT/ ORG cluster shows that most of the knowledge inflow seems to be concentrated on the management journals, rather than the ORG and ENT journals.

Once again, the relative isolation of JPIM from the ENT journals is somewhat surprising. One possible explanation can be that despite its stated openness to research on start-ups and small/medium businesses, a majority of the research published in JPIM concentrates on large organizations. Journals in the OM domain seem to have a negligible influence on the research published in JPIM.

Over the last 20 years, JPIM has firmly established itself as a highly influential forum for knowledge exchange in the TIM domain. It often acts as a gatekeeper in this domain, importing more net knowledge from MKT and MGT/ENT/ORG domains, and exporting them to the TIM journals (and OM journals to a lesser extent). As JPIM strides toward being universally regarded as the premier multidisciplinary journal in new product development and innovation management, it will benefit greatly from casting a wider net to appeal to a broader community of innovation scholars.

Figure 2 .Figure 1 .

 21 Figure 2. Trends in the Citations of JPIM (in %) by Disciplinary Clusters (1994-2013)

Figure 3 .Figure 4 .

 34 Figure 3. Trends in Citations of Disciplinary Clusters (in Numbers) in JPIM (1994-2013)

Table 3 .

 3 Number of Citations of JPIM Minus Number of Citations by JPIM (by Disciplinary Cluster)

Figure 5 .

 5 Figure 5. Trends in the Difference Between Citation Flows to and From JPIM (1994-2013)

Table 1

 1

	presents the list of the Top 50 journals that
	cited JPIM most frequently over the 1994-2013 pe-
	riod. JPIM was cited 15,756 times over this period in
	our database of 336 business journals. Of these, 4,300
	were self-citations (27.3%), and the remaining 11,456
	(72.7%) citations came from other sources. The 49
	other journals listed in Table 1 cited JPIM 9,683 times
	(61.5%). Together, these 50 journals accounted for
	88.8% of all citations received by JPIM from 1994 to
	2013.
	The Top 50 journals citing JPIM were then catego-
	rized in six clusters based on disciplinary domains:
	Technology and Innovation Management (TIM),
	Marketing (MKT), Operations Management (OM),
	Management (MGT), Organization Science (ORG),
	and Entrepreneurship (ENT). While Table 2 makes a

BIOGRAPHICAL SKETCHES Dr. Shikhar Sarin is

  a professor of marketing at Boise State University (USA) and Waikato Management School, University of Waikato. His research interests include marketing strategy, new product development, innovation, marketing/management of technology, personal selling & sales management, and digital commerce. He has received research awards from the American Marketing Association, Product Development and Management Association, and the Sales Education Foundation. His research has been published in Journal of Marketing, Journal of Marketing Research, Journal of the Academy of Marketing Science, Decision Sciences, Journal of Product Innovation Management, Industrial Marketing Management, Journal of Marketing Theory and Practice, Journal of Personal Selling and Sales Management, and Engineering Economist, among others. Dr. Christophe Haon is a professor of marketing at Grenoble Ecole de Management-Université Grenoble Alpes ComUE and a researcher at IREGE (Université Savoie Mont Blanc). He conducts research on marketing strategy, new product development, market orientation, and customer satisfaction. His research has been published in Marketing Letters, Journal of Business Research, Journal of Product Innovation Management, Industrial Marketing Management, and the European Management Review, among others. He has also coauthored several books, including Making Innovation Last: Sustainable Strategies for Long Term Growth, published by Palgrave Macmillan.

Dr. Mustapha Belkhouja is

  an associate professor of quantitative methods at Grenoble Ecole de Management-Université Grenoble Alpes ComUE. His research topics focus on academic visibility, knowledge diffusion, reputation, and international business. His research has appeared in Journal of Product Innovation Management, Industrial Marketing Management, M@n@ gement, Research Policy, Technological Forecasting & Social Change, and Strategic Organization, among others.

Table 1 . Identification of the 50 Journals Citing JPIM the Most from 1994 to 2013

 1

		Citations of JPIM	Citations by JPIM
		(Incoming Citations)	(Outgoing Citations)
	Journals	1994-2013	1994-2013	Balance
	Journal of Product Innovation Management	4,300	4,300	0
	Industrial Marketing Management	929	450	479
	Technovation	892	121	771
	R & D Management	722	305	417
	IEEE Transactions on Engineering Management	664	385	279
	International Journal of Technology Management	459	71	388
	Journal of Business Research	420	252	168
	Journal of Engineering and Technology Management	401	114	287
	Journal of The Academy of Marketing Science	341	422	-81
	Research Policy	313	610	-297
	International Journal of Operations & Production	272	74	198
	Management
	Journal of Operations Management	253	209	44
	Creativity and Innovation Management	244	43	201
	Journal of Marketing	240	2,012	-1,772
	Research-Technology Management	226	311	-85
	Technological Forecasting and Social Change	223	38	185
	Technology Analysis & Strategic Management	189	32	157
	Journal of Business & Industrial Marketing	187	35	152
	European Journal of Marketing	173	146	27
	Management Science	157	1,092	-935
	International Journal of Research in Marketing	146	181	-35
	Journal of Marketing Research	145	1,523	-1,378
	International Journal of Project Management	145	21	124
	Journal of International Marketing	140	53	87
	Decision Sciences	126	100	26
	Journal of Business Venturing	109	186	-77
	Long Range Planning	100	76	24
	Journal of Service Management	95	1	94
	Innovation-Management Policy & Practice	90	6	84
	Strategic Management Journal	78	1,468	-1,390
	Organization Science	77	668	-591
	International Marketing Review	74	55	19
	Project Management Journal	74	28	46
	Journal of Small Business Management	72	21	51
	Marketing Science	71	373	-302
	Industry and Innovation	70	6	64
	Journal of Supply Chain Management	69	8	61
	Marketing Letters	65	67	-2
	Journal of Service Research	63	41	22
	Asian Journal of Technology Innovation	57	0	57
	Academy of Management Journal	57	753	-696
	International Journal of Market Research	56	8	48
	Journal of Services Marketing	53	29	24
	EMJ-Engineering Management Journal	51	17	34
	California Management Review	50	349	-299
	Journal of Management & Organization	50	1	49
	Supply Chain Management-an International Journal	50	10	40
	British Journal of Management	49	24	25
	Journal of Management Studies	48	149	-101
	Journal of Knowledge Management	48	5

all the citations received by JPIM between 1994 and 2013. Besides self-citations, Technovation (5.7% of all JPIM citations), R&D Management (4.6%), and IEEE Transaction on Engineering Management (4.2%) were the TIM journals citing JPIM the most, while Industrial Marketing Management (5.8%), Journal

Table 2 . Categorization of Top 50 Journals Citing JPIM by Disciplinary Clusters

 2 of Business Research (2.7%), and the Journal of the Academy of Marketing Science (2.2%) featured prominently among the non-TIM journals in the top quintile of Table1.Operations Management journals: International Journal of Production Management (1.7%) and Journal of Operations Management (1.6%) make their appearance in the second quintile of Table1. Surprisingly, management journals (i.e., Management Science, Decision Sciences, Long Range Planning, and Strategic Management Journal) only appear toward the bottom of the second quintile, and in the third quintile of Table

	Technology and		Operations
	Innovation		Management
	Management (TIM)	Marketing (MKT)	(OM)

Management

(MGT) Organization Science (ORG) Entrepreneurship (ENT) Journal of Product Innovation Management Industrial Marketing Management International Journal of Operations & Production Management Management Science Organization Science Journal of Business Venturing Technovation Journal of Business Research


Andrea Olivo

Frédéric Grosshans

Optimality of linear optical Bell measurements How much can ancillae help?

Keywords: static linear optics Why? Because, •, experimentally easier: no feedforward λ

|ϕ + ⟩ = 1 √ 2 ( |00⟩ + |11⟩ ) |ψ + ⟩ = 1 √ 2 ( |01⟩ + |10⟩ ) |ϕ -⟩ = 1 √ 2 ( |00⟩ -|11⟩ ) |ψ -⟩ = 1 √ 2 ( |01⟩ -|10⟩ )
Bell Measurement Projective measurement on the Bell basis Unambiguous Outcome never wrong, but can fail with probability P fail

The task: unambiguous Bell measurement

|ϕ + ⟩ = 1 √ 2 ( |00⟩ + |11⟩ ) |ψ + ⟩ = 1 √ 2 ( |01⟩ + |10⟩ ) |ϕ -⟩ = 1 √ 2 ( |00⟩ -|11⟩ ) |ψ -⟩ = 1 √ 2 ( |01⟩ -
λ /2 λ /2 c = Ua . . . a =       a † 0 a † 1 . . . a † n       . . . c = [ c † 0 c † 1 . . . c † n ]
[Braunstein and Mann, 1995]

• Known P succ =

|β i ⟩ |ψ + ⟩ -→ 1 √ 2 (|1100⟩ + |0011⟩) |ψ -⟩ -→ 1 √ 2 (|1001⟩ -|0110⟩) |ϕ ± ⟩ -→ i 2 ( |2000⟩ ± |0200⟩ + |0020⟩ ± |0002⟩)
Beyond 1/2 What can we say about their optimality?

Our work

Ideally, we want an upper bound on P succ depending on the ancilla.

We provide:

Ideally, we want an upper bound on P succ depending on the ancilla.

We provide:

• An analytical bound for polarization-preserving interferometers

Our work

Ideally, we want an upper bound on P succ depending on the ancilla.

We provide:

• An analytical bound for polarization-preserving interferometers

• A thorough numerical search for generic (small) interferometers

Analytical upper bound

Overview of the proof . . .

U |β i ⟩ |Υ⟩ Input: |Ψ in ⟩ = |β i ⟩ |Υ⟩, with |Υ⟩ = ∑ k λ=0 v λ |Υ, λ⟩ a k-photon ancilla Each |Υ,

Upper bounds

Ancilla polarization-based upper bound:

P fail ≥ 1 2 ( max λ even |v λ | 2 + max λ odd |v λ | 2 ) (1)
(looser) Photon number-based upper bound:

P fail ≥ 1 ⌈k + 1⌉ even (2)
N.B. The Grice's schemes saturate both bounds!

Linear network optimizer Polynomial representation

Second quantization, n-modes interferometer.

Input/output state -→ polynomial in the input/output mode operators:

|ψ in ⟩ = P in (a † 1 , . . . , a † n ) |0⟩ |ψ out ⟩ = P out (c † 1 , . . . , c † n ) |0⟩
Action of the interferometer on |ψ in ⟩ -→ unitary transformation U acting on the mode operators: Above steps are automatic symbolic computation. Then:

a † i = n ∑ j=1 u ij c † j Measurement of
3. Functions p e i (U) are hardcoded in C 4. A f.o.m. f(U) is numerically optimized over U(n) n = 4, k = 0 P in = 1 √ 2 (a † 1 a † 3 + a † 2 a † 4 ) ↓ P out = 1 √ 2 ( ∑ j1 u 1j1 c † j1 )( ∑ j2 u 3j2 c † j2 ) + 1 √ 2 ( ∑ j3 u 2j3 c † j3 )( ∑ j4 u 4j4 c † j4 ) n = 4, k = 0 P in = 1 √ 2 (a † 1 a † 3 + a † 2 a † 4 ) ↓ P out = 1 √ 2 ( ∑ j1 u 1j1 c † j1 )( ∑ j2 u 3j2 c † j2 ) + 1 √ 2 ( ∑ j3 u 2j3 c † j3 )( ∑ j4 u 4j4 c † j4 ) ↓ u 11 u 31 +
+ u 24 u 43 )/ √ 2 n = 4, k = 0 P in = 1 √ 2 (a † 1 a † 3 + a † 2 a † 4 ) ↓ P out = 1 √ 2 ( ∑ j1 u 1j1 c † j1 )( ∑ j2 u 3j2 c † j2 ) + 1 √ 2 ( ∑ j3 u 2j3 c † j3 )( ∑ j4 u 4j4 c † j4 ) ↓ u 11 u 31 +

  λ⟩ is a state with λ horizontally polarized photons . . . under a projective measurement of the horizontally-polarized photon number of |Ψ out ⟩ |ψ + ⟩, |ψ -⟩ and |ϕ ± ⟩ are mapped in three orthogonal subspaces ∀λ . . . post-measurement states |Λ ± ⟩ corresponding to |ϕ + ⟩ and |ϕ -⟩ can be discriminated with optimal P succ ≤ 1 -| ⟨Λ + |Λ -⟩ |.

  |ψ out ⟩ by an array of PNRD. Detection event -→ a configuration of clicks at the output. Task: maximize P succ over all possible n-modes interferometers, using k-photon ancilla |Υ⟩ Task: maximize P succ over all possible n-modes interferometers, using k-photon ancilla |Υ⟩ 1. For each |ψ in ⟩ = |β i ⟩ |Υ⟩ -→ 2 nd quantization output polynomial 2. Functions p e i (U) -→ probability of detection event e for input β i Above steps are automatic symbolic computation. Then: Task: maximize P succ over all possible n-modes interferometers, using k-photon ancilla |Υ⟩ 1. For each |ψ in ⟩ = |β i ⟩ |Υ⟩ -→ 2 nd quantization output polynomial 2. Functions p e i (U) -→ probability of detection event e for input β i Above steps are automatic symbolic computation. Then: 3. Functions p e i (U) are hardcoded in C Task: maximize P succ over all possible n-modes interferometers, using k-photon ancilla |Υ⟩ 1. For each |ψ in ⟩ = |β i ⟩ |Υ⟩ -→ 2 nd quantization output polynomial 2. Functions p e i (U) -→ probability of detection event e for input β i

  u 21 u 41 u 12 u 32 + u 22 u 42 u 13 u 33 + u 23 u 43 u 14 u 34 + u 24 u 44 (u 11 u 32 + u 12 u 31 + u 21 u 42 + u 22 u 41 )/ √ 2 (u 11 u 33 + u 13 u 31 + u 21 u 43 + u 23 u 41 )/ √ 2 (u 11 u 34 + u 14 u 31 + u 21 u 44 + u 24 u 41 )/ √ 2 (u 12 u 33 + u 13 u 32 + u 22 u 43 + u 23 u 42 )/ √ 2 (u 12 u 34 + u 14 u 32 + u 22 u 44 + u 24 u 42 )/ √ 2 (u 13 u 34 + u 14 u 33 + u 23 u 44

  u 21 u 41 u 12 u 32 + u 22 u 42 u 13 u 33 + u 23 u 43 u 14 u 34 + u 24 u 44 (u 11 u 32 + u 12 u 31 + u 21 u 42 + u 22 u 41 )/ √ 2 (u 11 u 33 + u 13 u 31 + u 21 u 43 + u 23 u 41 )/ √ 2 (u 11 u 34 + u 14 u 31 + u 21 u 44 + u 24 u 41 )/ √ 2 (u 12 u 33 + u 13 u 32 + u 22 u 43 + u 23 u 42 )/ √ 2 (u 12 u 34 + u 14 u 32 + u 22 u 44 + u 24 u 42 )/ √ 2 (u 13 u 34 + u 14 u 33 + u 23 u 44 + u 24 u 43 )/ Bell pairs: no better than one Bell pair • 3 to N Bell pairs: out of reach with 12 cores, 256GB RAM cluster • Pol. pres. bound predicts P fail ≳ Bell pairs: no better than one Bell pair • 3 to N Bell pairs: out of reach with 12 cores, 256GB RAM cluster • Pol. pres. bound predicts P fail ≳

	More single, unentangled photons The "half"-Ewert & van Loock scheme Entangled ancillae Entangled ancillae Entangled ancillae
	Why not using pen and paper for p e i (U)? k photons Pol. Pres. bound Num. search Explicit scheme k photons Pol. Pres. bound Num. search Explicit scheme
	For (small!) 3 4 Grice's scheme: 2 5/8 2 5/8 Do entangled ancillae help? Do entangled ancillae help? Do entangled ancillae help?	5/8 5/8	5/8 5/8
	Total number of functions 1320 Independent just 5 But 2 nd iteration, 7 8 : Total number of functions 490314 Independent Total number of terms 1,8 • 10 6 just 2 single photons beat 50% limit! |1⟩ |1⟩ 22 4 3/4 3/4 |β i ⟩ 4 3/4 3/4 • Grice's one-Bell-pair: optimal 3 4 , by numerical search 3/4 3/4 • Grice's one-Bell-pair: optimal 3 4 , by numerical search • Grice's one-Bell-pair: optimal 3 4 , by numerical search Results 6 13/16 3/4 -8 25/32 -49/64 12 13/16 -25/32 6 13/16 3/4 -8 25/32 -49/64 12 13/16 -λ /2 λ /2 P succ = 5 8 • 2 Bell pairs: no better than one Bell pair • 3 to N Bell pairs: out of reach with 12 cores, 256GB RAM cluster • Pol. pres. bound predicts P fail ≳ 1 √ πk ≥ 1 k • 2 1 √ πk ≥ 1 k • 2 1 √ πk 1 ≥ k 25/32 • Grice's 7
	√ 2 Also independently found by Ewert & van Loock

8 scheme needs n = 16, k = 6: barely out of reach

For each |ψ in ⟩ = |β i ⟩ |Υ⟩ -→ 2 nd quantization output polynomial

An example: no ancilla on |ϕ + ⟩ n = 4, k = 0

Optimization: a case for symbolic computation

Why not using pen and paper for p e i (U)? For (small!) 3 4 Grice's scheme:

Total number of functions 1320 Independent just 5

Simplest type of ancilla, no known scheme We find no advantage using just one extra photon.

Do entangled ancillae help?

• Grice's one-Bell-pair: optimal 3 4 , by numerical search

Conclusion Achievements

What can we say on the optimal P succ of unambiguous Bell measurement?

• Upper bound for polarization-preserving interferometers, saturated by known schemes

• Hybrid numerical/symbolical search

• Confirms optimality of (some) known schemes • New 2-photon scheme with Psucc = 5 8

• Explored several ancillae-→ 3 4 stays the best (for small networks)

Thank you


Keywords:

The framework: static linear optics Why? Because... • ...

The task: unambiguous Bell measurement

|ϕ + ⟩ = 1 √ 2 ( |00⟩ + |11⟩ ) |ψ + ⟩ = 1 √ 2 ( |01⟩ + |10⟩ ) |ϕ -⟩ = 1 √ 2 ( |00⟩ -|11⟩ ) |ψ -⟩ = 1 √ 2 ( |01⟩ -|10⟩ )
Bell Measurement Projective measurement on the Bell basis Unambiguous Outcome never wrong, but can fail with probability P fail

|ϕ + ⟩ = 1 √ 2 ( |00⟩ + |11⟩ ) |ψ + ⟩ = 1 √ 2 ( |01⟩ + |10⟩ ) |ϕ -⟩ = 1 √ 2 ( |00⟩ -|11⟩ ) |ψ -⟩ = 1 √ 2 ( |01⟩ -
λ /2 λ /2 c = Ua . . . a =       a † 0 a † 1 . . . a † n       . . . c = [ c † 0 c † 1 . . . c † n ]
[Braunstein and Mann, 1995]

• Known P succ =

|β i ⟩ |ψ + ⟩ -→ 1 √ 2 (|1100⟩ + |0011⟩) |ψ -⟩ -→ 1 √ 2 (|1001⟩ -|0110⟩) |ϕ ± ⟩ -→ i 2 ( |2000⟩ ± |0200⟩ + |0020⟩ ± |0002⟩)
[Grice, 2011]

• P succ = with an extra |ϕ + ⟩ as ancilla

• P fail = -N with GHZ-like states of 2 N -2 photons
Beyond 1/2 What can we say about their optimality?

Ideally, we want an upper bound on P succ depending on the ancilla.

We provide:

• An analytical bound for polarization-preserving interferometers

Our work

Ideally, we want an upper bound on P succ depending on the ancilla.

We provide:

• An analytical bound for polarization-preserving interferometers

• A thorough numerical search for generic (small) interferometers 5 Analytical upper bound . . .

U |β i ⟩ |Υ⟩ Input: |Ψ in ⟩ = |β i ⟩ |Υ⟩, with |Υ⟩ = ∑ k λ=0 v λ |Υ, λ⟩ a k-photon ancilla Each |Υ,

Upper bounds

Ancilla polarization-based upper bound:

P fail ≥ 1 2 ( max λ even |v λ | 2 + max λ odd |v λ | 2 ) (1)
(looser) Photon number-based upper bound:

P fail ≥ 1 ⌈k + 1⌉ even (2)
N.B. The Grice's schemes saturate both bounds!

Linear network optimizer Polynomial representation

Second quantization, n-modes interferometer.

Input/output state -→ polynomial in the input/output mode operators:

|ψ in ⟩ = P in (a † 1 , . . . , a † n ) |0⟩ |ψ out ⟩ = P out (c † 1 , . . . , c † n ) |0⟩
Action of the interferometer on |ψ in ⟩ -→ unitary transformation U acting on the mode operators: Above steps are automatic symbolic computation. Then:

a † i = n ∑ j=1 u ij c † j Measurement of
3. Functions p e i (U) are hardcoded in C 4. A f.o.m. f(U) is numerically optimized over U(n) n = 4, k = 0 P in = 1 √ 2 (a † 1 a † 3 + a † 2 a † 4 ) ↓ P out = 1 √ 2 ( ∑ j1 u 1j1 c † j1 )( ∑ j2 u 3j2 c † j2 ) + 1 √ 2 ( ∑ j3 u 2j3 c † j3 )( ∑ j4 u 4j4 c † j4 ) ↓ u 11 u 31 +
+ u 24 u 43 )/ √ 2 n = 4, k = 0 P in = 1 √ 2 (a † 1 a † 3 + a † 2 a † 4 ) ↓ P out = 1 √ 2 ( ∑ j1 u 1j1 c † j1 )( ∑ j2 u 3j2 c † j2 ) + 1 √ 2 ( ∑ j3 u 2j3 c † j3 )( ∑ j4 u 4j4 c † j4 ) ↓ u 11 u 31 +

Conclusion Achievements

What can we say on the optimal P succ of unambiguous Bell measurement?

• Upper bound for polarization-preserving interferometers, saturated by known schemes

• Hybrid numerical/symbolical search

• Confirms optimality of (some) known schemes • New 2-photon scheme with Psucc = 5 8

• Explored several ancillae-→ 3 4 stays the best (for small networks)

  λ⟩ is a state with λ horizontally polarized photons . . . under a projective measurement of the horizontally-polarized photon number of |Ψ out ⟩ |ψ + ⟩, |ψ -⟩ and |ϕ ± ⟩ are mapped in three orthogonal subspaces ∀λ . . . post-measurement states |Λ ± ⟩ corresponding to |ϕ + ⟩ and |ϕ -⟩ can be discriminated with optimal P succ ≤ 1 -| ⟨Λ + |Λ -⟩ |.

  |ψ out ⟩ by an array of PNRD. Detection event -→ a configuration of clicks at the output. Task: maximize P succ over all possible n-modes interferometers, using k-photon ancilla |Υ⟩ Task: maximize P succ over all possible n-modes interferometers, using k-photon ancilla |Υ⟩ 1. For each |ψ in ⟩ = |β i ⟩ |Υ⟩ -→ 2 nd quantization output polynomial 2. Functions p e i (U) -→ probability of detection event e for input β i Above steps are automatic symbolic computation. Then: 3. Functions p e i (U) are hardcoded in C Task: maximize P succ over all possible n-modes interferometers, using k-photon ancilla |Υ⟩ 1. For each |ψ in ⟩ = |β i ⟩ |Υ⟩ -→ 2 nd quantization output polynomial 2. Functions p e i (U) -→ probability of detection event e for input β i

  u 21 u 41 u 12 u 32 + u 22 u 42 u 13 u 33 + u 23 u 43 u 14 u 34 + u 24 u 44 (u 11 u 32 + u 12 u 31 + u 21 u 42 + u 22 u 41 )/ √ 2 (u 11 u 33 + u 13 u 31 + u 21 u 43 + u 23 u 41 )/ √ 2 (u 11 u 34 + u 14 u 31 + u 21 u 44 + u 24 u 41 )/ √ 2 (u 12 u 33 + u 13 u 32 + u 22 u 43 + u 23 u 42 )/ √ 2 (u 12 u 34 + u 14 u 32 + u 22 u 44 + u 24 u 42 )/ √ 2 (u 13 u 34 + u 14 u 33 + u 23 u 44

  u 21 u 41 u 12 u 32 + u 22 u 42 u 13 u 33 + u 23 u 43 u 14 u 34 + u 24 u 44 (u 11 u 32 + u 12 u 31 + u 21 u 42 + u 22 u 41 )/ √ 2 (u 11 u 33 + u 13 u 31 + u 21 u 43 + u 23 u 41 )/ √ 2 (u 11 u 34 + u 14 u 31 + u 21 u 44 + u 24 u 41 )/ √ 2 (u 12 u 33 + u 13 u 32 + u 22 u 43 + u 23 u 42 )/ √ 2 (u 12 u 34 + u 14 u 32 + u 22 u 44 + u 24 u 42 )/ √ 2 (u 13 u 34 + u 14 u 33 + u 23 u 44 + u 24 u 43 )/ Bell pairs: no better than one Bell pair • 3 to N Bell pairs: out of reach with 12 cores, 256GB RAM cluster • Pol. pres. bound predicts P fail ≳

	More single, unentangled photons The "half"-Ewert & van Loock scheme Entangled ancillae
	Why not using pen and paper for p e i (U)? k photons Pol. Pres. bound Num. search Explicit scheme k photons Pol. Pres. bound Num. search Explicit scheme
	For (small!) 3 4 Grice's scheme: 2 5/8 2 5/8 Do entangled ancillae help?	5/8 5/8	5/8 5/8
	Total number of functions 1320 Independent just 5 But 2 nd iteration, 7 8 : Total number of functions 490314 Independent Total number of terms 1,8 • 10 6 just 2 single photons beat 50% limit! |1⟩ |1⟩ 22 4 3/4 3/4 |β i ⟩ 4 3/4 3/4 • Grice's one-Bell-pair: optimal 3 4 , by numerical search 3/4 3/4 • Grice's one-Bell-pair: optimal 3 4 , by numerical search Results 6 13/16 3/4 -8 25/32 -49/64 12 13/16 -25/32 6 13/16 3/4 -8 25/32 -49/64 12 13/16 -λ /2 λ /2 P succ = 5 8 • 2 Bell pairs: no better than one Bell pair • 3 to N Bell pairs: out of reach with 12 cores, 256GB RAM cluster • Pol. pres. bound predicts P fail ≳ 1 √ πk > 1 k • 2 1 √ πk 1 > k 25/32 • Grice's 7
	√ 2 Also independently found by Ewert & van Loock

8 scheme needs n = 16, k = 6: barely out of reach

For each |ψ in ⟩ = |β i ⟩ |Υ⟩ -→ 2 nd quantization output polynomial

An example: no ancilla on |ϕ + ⟩ n = 4, k = 0

Optimization: a case for symbolic computation

Why not using pen and paper for p e i (U)? For (small!) 3 4 Grice's scheme:

Total number of functions 1320 Independent just 5

Simplest type of ancilla, no known scheme We find no advantage using just one extra photon.

Do entangled ancillae help?

• Grice's one-Bell-pair: optimal 3 4 , by numerical search

We have automated second quantization simulator, up to 10 modes and 8 photons.

• Include noise. But how to generalize "unambiguous"?

• Adapt for state generation problem

Thank you


The applications

Keywords:

The framework: static linear optics Why? Because... • ...

The task: unambiguous Bell measurement

|ϕ + ⟩ = 1 √ 2 ( |00⟩ + |11⟩ ) |ψ + ⟩ = 1 √ 2 ( |01⟩ + |10⟩ ) |ϕ -⟩ = 1 √ 2 ( |00⟩ -|11⟩ ) |ψ -⟩ = 1 √ 2 ( |01⟩ -|10⟩ )
Bell Measurement Projective measurement on the Bell basis Unambiguous Outcome never wrong, but can fail with probability P fail

|ϕ + ⟩ = 1 √ 2 ( |00⟩ + |11⟩ ) |ψ + ⟩ = 1 √ 2 ( |01⟩ + |10⟩ ) |ϕ -⟩ = 1 √ 2 ( |00⟩ -|11⟩ ) |ψ -⟩ = 1 √ 2 ( |01⟩ -
λ /2 λ /2 c = Ua . . . a =       a † 0 a † 1 . . . a † n       . . . c = [ c † 0 c † 1 . . . c † n ]
[ Braunstein and Mann, 1995] • Known P succ = 1 2 scheme [Braunstein & Mann, 1995] • Optimal, even with feedforward [Calsamiglia & Lütkenhaus, 2001]

|β i ⟩ |ψ + ⟩ -→ 1 √ 2 (|1100⟩ + |0011⟩) |ψ -⟩ -→ 1 √ 2 (|1001⟩ -|0110⟩) |ϕ ± ⟩ -→ i 2 ( |2000⟩ ± |0200⟩ + |0020⟩ ± |0002⟩)
Beyond 1/2

[Grice, 2011]

• P succ = with an extra |ϕ + ⟩ as ancilla

• P fail = -N with GHZ-like states of 2 N -2 photons
Beyond 1/2 What can we say about their optimality?

Ideally, we want an upper bound on P succ depending on the ancilla.

We provide:

• An analytical bound for polarization-preserving interferometers

Our work

Ideally, we want an upper bound on P succ depending on the ancilla.

We provide:

• An analytical bound for polarization-preserving interferometers

• A thorough numerical search for generic (small) interferometers

Analytical upper bound

Overview of the proof . . .

U |β i ⟩ |Υ⟩ Input: |Ψ in ⟩ = |β i ⟩ |Υ⟩, with |Υ⟩ = ∑ k λ=0 v λ |Υ, λ⟩ a k-photon ancilla Each |Υ,

Upper bounds

Ancilla polarization-based upper bound:

P fail ≥ 1 2 ( max λ even |v λ | 2 + max λ odd |v λ | 2 ) (1)
(looser) Photon number-based upper bound:

P fail ≥ 1 ⌈k + 1⌉ even (2)
N.B. The Grice's schemes saturate both bounds!

Linear network optimizer Polynomial representation

Second quantization, n-modes interferometer.

Input/output state -→ polynomial in the input/output mode operators:

|ψ in ⟩ = P in (a † 1 , . . . , a † n ) |0⟩ |ψ out ⟩ = P out (c † 1 , . . . , c † n ) |0⟩
Action of the interferometer on |ψ in ⟩ -→ unitary transformation U acting on the mode operators: Above steps are automatic symbolic computation. Then: Optimization: a case for symbolic computation

a † i = n ∑ j=1 u ij c † j Measurement of |ψ out ⟩
3. Functions p e i (U) are hardcoded in C 4. A f.o.m. f(U) is numerically optimized over U(n) n = 4, k = 0 P in = 1 √ 2 (a † 1 a † 3 + a † 2 a † 4 ) ↓ P out = 1 √ 2 ( ∑ j1 u 1j1 c † j1 )( ∑ j2 u 3j2 c † j2 ) + 1 √ 2 ( ∑ j3 u 2j3 c † j3 )( ∑ j4 u 4j4 c † j4 ) ↓ u 11 u 31 +
+ u 24 u 43 )/ √ 2 n = 4, k = 0 P in = 1 √ 2 (a † 1 a † 3 + a † 2 a † 4 ) ↓ P out = 1 √ 2 ( ∑ j1 u 1j1 c † j1 )( ∑ j2 u 3j2 c † j2 ) + 1 √ 2 ( ∑ j3 u 2j3 c † j3 )( ∑ j4 u 4j4 c † j4 ) ↓ u 11 u 31 +
Why not using pen and paper for p e i (U)? For (small!) 3 4 Grice's scheme:

Total number of functions 1320 Independent just 5

Why not using pen and paper for p e i (U)? For (small!) 3 4 Grice's scheme:

Total number of functions 1320 Independent just 5

But 2 nd iteration, 7 8 :

Total number of functions 490314 Independent 22

Total number of terms 1,8

Conclusion Achievements

What can we say on the optimal P succ of unambiguous Bell measurement?

• Upper bound for polarization-preserving interferometers, saturated by known schemes

• Hybrid numerical/symbolical search

• Confirms optimality of (some) known schemes • New 2-photon scheme with Psucc = 5 8

• Explored several ancillae-→ 3 4 stays the best (for small networks)

  λ⟩ is a state with λ horizontally polarized photons . under a projective measurement of the horizontally-polarized photon number of |Ψ out ⟩ , |ψ -⟩ and |ϕ ± ⟩ are mapped in three orthogonal subspaces ∀λ post-measurement states |Λ ± ⟩ corresponding to |ϕ + ⟩ and |ϕ -⟩ can be discriminated with optimal P succ ≤ 1 -| ⟨Λ + |Λ -⟩ |.

  by an array of PNRD. Detection event -→ a configuration of clicks at the output. Task: maximize P succ over all possible n-modes interferometers, using k-photon ancilla |Υ⟩ 1. For each |ψ in ⟩ = |β i ⟩ |Υ⟩ -→ 2 nd quantization output polynomial Task: maximize P succ over all possible n-modes interferometers, using k-photon ancilla |Υ⟩ 1. For each |ψ in ⟩ = |β i ⟩ |Υ⟩ -→ 2 nd quantization output polynomial 2. Functions p e i (U) -→ probability of detection event e for input β i Task: maximize P succ over all possible n-modes interferometers, using k-photon ancilla |Υ⟩ 1. For each |ψ in ⟩ = |β i ⟩ |Υ⟩ -→ 2 nd quantization output polynomial 2. Functions p e i (U) -→ probability of detection event e for input β i Above steps are automatic symbolic computation. Then: Task: maximize P succ over all possible n-modes interferometers, using k-photon ancilla |Υ⟩ 1. For each |ψ in ⟩ = |β i ⟩ |Υ⟩ -→ 2 nd quantization output polynomial 2. Functions p e i (U) -→ probability of detection event e for input β i Above steps are automatic symbolic computation. Then: 3. Functions p e i (U) are hardcoded in C Task: maximize P succ over all possible n-modes interferometers, using k-photon ancilla |Υ⟩ 1. For each |ψ in ⟩ = |β i ⟩ |Υ⟩ -→ 2 nd quantization output polynomial 2. Functions p e i (U) -→ probability of detection event e for input β i

  u 21 u 41 u 12 u 32 + u 22 u 42 u 13 u 33 + u 23 u 43 u 14 u 34 + u 24 u 44 (u 11 u 32 + u 12 u 31 + u 21 u 42 + u 22 u 41 )/ √ 2 (u 11 u 33 + u 13 u 31 + u 21 u 43 + u 23 u 41 )/ √ 2 (u 11 u 34 + u 14 u 31 + u 21 u 44 + u 24 u 41 )/ √ 2 (u 12 u 33 + u 13 u 32 + u 22 u 43 + u 23 u 42 )/ √ 2 (u 12 u 34 + u 14 u 32 + u 22 u 44 + u 24 u 42 )/ √ 2 (u 13 u 34 + u 14 u 33 + u 23 u 44

  u 21 u 41 u 12 u 32 + u 22 u 42 u 13 u 33 + u 23 u 43 u 14 u 34 + u 24 u 44 (u 11 u 32 + u 12 u 31 + u 21 u 42 + u 22 u 41 )/ √ 2 (u 11 u 33 + u 13 u 31 + u 21 u 43 + u 23 u 41 )/ √ 2 (u 11 u 34 + u 14 u 31 + u 21 u 44 + u 24 u 41 )/ √ 2 (u 12 u 33 + u 13 u 32 + u 22 u 43 + u 23 u 42 )/ √ 2 (u 12 u 34 + u 14 u 32 + u 22 u 44 + u 24 u 42 )/ √ 2 (u 13 u 34 + u 14 u 33 + u 23 u 44 + u 24 u 43 )/ √ 2

  • 10 6 Bell pairs: no better than one Bell pair • 3 to N Bell pairs: out of reach with 12 cores, 256GB RAM cluster • Pol. pres. bound predicts P fail ≳

	More single, unentangled photons The "half"-Ewert & van Loock scheme Entangled ancillae Entangled ancillae
	k photons Pol. Pres. bound Num. search Explicit scheme
	2 Do entangled ancillae help? 5/8 Do entangled ancillae help?	5/8	5/8
	4 • Grice's one-Bell-pair: optimal 3 3/4 4 , by numerical search 3/4 3/4 • Grice's one-Bell-pair: optimal 3 4 , by numerical search
	6 8 12 • 2 Bell pairs: no better than one Bell pair 13/16 3/4 25/32 -13/16 -λ /2 λ /2 • 3 to N Bell pairs: out of reach with 12 cores, 256GB RAM cluster -49/64 P succ = 5 8 • Pol. pres. bound predicts P fail ≳ 1 √ πk > 1 k • 2 1 √ πk 1 > k 25/32 • Grice's 7
	just 2 single photons beat 50% limit! |1⟩ |1⟩	|β i ⟩
	Also independently found by Ewert & van Loock

8 scheme needs n = 16, k = 6: barely out of reach

Results

Simplest type of ancilla, no known scheme